En geometría , un conjunto K ⊂ R d se define como ortogonalmente convexo si, para cada línea L que es paralela a uno de los vectores base estándar , la intersección de K con L está vacía, es un punto o un solo segmento . El término "ortogonal" se refiere a las bases cartesianas y coordenadas correspondientes en el espacio euclidiano , donde los diferentes vectores base son perpendiculares , así como a las líneas correspondientes. A diferencia de los conjuntos convexos ordinarios , un conjunto ortogonalmente convexo no es necesariamente conexo .
La envoltura convexa ortogonal de un conjunto K ⊂ R d es la intersección de todos los superconjuntos ortogonalmente convexos conectados de K .
Estas definiciones se hacen por analogía con la teoría clásica de la convexidad, en la que K es convexo si, para cada línea L , la intersección de K con L es vacía, un punto o un solo segmento. La convexidad ortogonal restringe las líneas para las que se requiere que se cumpla esta propiedad, por lo que cada conjunto convexo es ortogonalmente convexo pero no viceversa. Por la misma razón, la envoltura convexa ortogonal en sí misma es un subconjunto de la envoltura convexa del mismo conjunto de puntos. Un punto p pertenece a la envoltura convexa ortogonal de K si y solo si cada uno de los ortantes cerrados alineados con el eje que tienen p como vértice tiene una intersección no vacía con K .
La envoltura convexa ortogonal también se conoce como envoltura convexa rectilínea o, en dos dimensiones , envoltura convexa x - y .
La figura muestra un conjunto de 16 puntos en el plano y la envoltura convexa ortogonal de estos puntos. Como se puede ver en la figura, la envoltura convexa ortogonal es un polígono con algunas aristas degeneradas que conectan vértices extremos en cada dirección de coordenadas. Para un conjunto de puntos discretos como este, todas las aristas de la envoltura convexa ortogonal son horizontales o verticales. En este ejemplo, la envoltura convexa ortogonal está conectada.
A diferencia de la convexidad clásica, donde existen varias definiciones equivalentes de la envoltura convexa, las definiciones de la envoltura convexa ortogonal realizadas por analogía con las de la envoltura convexa dan como resultado objetos geométricos diferentes. Hasta ahora, los investigadores han explorado las siguientes cuatro definiciones de la envoltura convexa ortogonal de un conjunto :
En las figuras de la derecha, la figura superior muestra un conjunto de seis puntos en el plano. La envoltura convexa ortogonal clásica del conjunto de puntos es el propio conjunto de puntos. De arriba a abajo, las figuras segunda a cuarta muestran, respectivamente, la envoltura convexa ortogonal máxima, la conexa y la funcional del conjunto de puntos. Como se puede ver, la envoltura convexa ortogonal es un polígono con algunas "aristas" degeneradas, es decir, cadenas poligonales alternas ortogonalmente convexas con ángulos interiores que conectan los vértices extremos.
La envoltura convexa ortogonal clásica puede definirse de manera equivalente como el superconjunto ortogonalmente convexo más pequeño de un conjunto , por analogía con la siguiente definición de envoltura convexa: la envoltura convexa de es el superconjunto convexo más pequeño de . La envoltura convexa ortogonal clásica puede estar desconectada. Si un conjunto de puntos no tiene ningún par de puntos en una línea paralela a uno de los vectores base estándar, la envoltura convexa ortogonal clásica de dicho conjunto de puntos es igual al propio conjunto de puntos.
Una propiedad bien conocida de las envolturas convexas se deriva del teorema de Carathéodory : un punto está en el interior de la envoltura convexa de un conjunto de puntos si, y solo si, ya está en la envoltura convexa de o menos puntos de . Esta propiedad también es válida para las envolturas convexas ortogonales clásicas.
Por definición, la envoltura convexa ortogonal conectada siempre está conectada. Sin embargo, no es única. Consideremos, por ejemplo, un par de puntos en el plano que no se encuentran sobre una línea horizontal o vertical. La envoltura convexa ortogonal conectada de tales puntos es una cadena poligonal alterna ortogonalmente convexa con un ángulo interior que conecta los puntos. Cualquier cadena poligonal de este tipo tiene la misma longitud, por lo que hay infinitas envolturas convexas ortogonales conectadas para el conjunto de puntos.
Para los conjuntos de puntos en el plano, la envoltura convexa ortogonal conexa se puede obtener fácilmente a partir de la envoltura convexa ortogonal máxima. Si la envoltura convexa ortogonal máxima de un conjunto de puntos es conexa, entonces es igual a la envoltura convexa ortogonal conexa de . Si este no es el caso, entonces hay infinitas envolturas convexas ortogonales conexas para , y cada una se puede obtener uniendo los componentes conexos de la envoltura convexa ortogonal máxima de con cadenas poligonales alternas ortogonalmente convexas con ángulo interior .
La envoltura convexa ortogonal funcional no se define utilizando propiedades de conjuntos, sino propiedades de funciones sobre conjuntos. Es decir, restringe la noción de función convexa de la siguiente manera. Una función se llama ortogonalmente convexa si su restricción a cada línea paralela a un vector base estándar distinto de cero es una función convexa.
Varios autores han estudiado algoritmos para construir envolventes convexas ortogonales: Montuno y Fournier (1982); Nicholl et al. (1983); Ottmann, Soisalon-Soininen y Wood (1984); Karlsson y Overmars (1988). Según los resultados de estos autores, la envolvente convexa ortogonal de n puntos en el plano puede construirse en un tiempo O ( n log n ) , o posiblemente más rápido utilizando estructuras de datos de búsqueda de enteros para puntos con coordenadas enteras .
Es natural generalizar la convexidad ortogonal a la convexidad de orientación restringida , en la que un conjunto K se define como convexo si todas las líneas que tienen una de un conjunto finito de pendientes deben intersecar K en subconjuntos conexos; véase, por ejemplo, Rawlins (1987), Rawlins y Wood (1987, 1988) o Fink y Wood (1996, 1998).
Además, el lapso ajustado de un espacio métrico finito está estrechamente relacionado con la envoltura convexa ortogonal. Si un conjunto de puntos finitos en el plano tiene una envoltura convexa ortogonal conectada, esa envoltura es el lapso ajustado para la distancia de Manhattan en el conjunto de puntos. Sin embargo, las envolturas ortogonales y los lapsos ajustados difieren para los conjuntos de puntos con envolturas ortogonales desconectadas o en espacios L p de dimensiones superiores .
O'Rourke (1993) describe varios otros resultados sobre la convexidad ortogonal y la visibilidad ortogonal .
