envoltura convexa ortogonal

En geometría , un conjunto $K \subset R d$ se define como ortogonalmente convexo si, para cada línea $L$ paralela a uno de los vectores base estándar , la intersección de $K$ con $L$ es vacía, un punto o un segmento único. El término "ortogonal" se refiere a la base cartesiana correspondiente y a las coordenadas 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 \subset R d$ es la intersección de todos los superconjuntos ortogonalmente convexos conectados de $K.$

Estas definiciones se basan en la 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 segmento único. La convexidad ortogonal restringe las líneas para las que se requiere que se cumpla esta propiedad, de modo que todo conjunto convexo es ortogonalmente convexo, pero no a la inversa. Por la misma razón, la envoltura convexa ortogonal 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 los ejes que tienen $a 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$ .

Ejemplo

La figura muestra un conjunto de 16 puntos en el plano y la envoltura convexa ortogonal de estos puntos. Como se puede observar, la envoltura convexa ortogonal es un polígono con aristas degeneradas que conectan vértices extremos en cada dirección de coordenadas. Para un conjunto de puntos discreto como este, todas las aristas de la envoltura convexa ortogonal son horizontales o verticales. En este ejemplo, la envoltura convexa ortogonal está conectada.

Definiciones alternativas

A diferencia de la convexidad clásica, donde existen varias definiciones equivalentes de la envoltura convexa, las definiciones de la envoltura convexa ortogonal, hechas 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. $K\subset \mathbb {R} ^{d}$ :

Definición máxima : La definición descrita en la introducción de este artículo. Se basa en los máximos de un conjunto de puntos .
Definición clásica : La envoltura convexa ortogonal de $K$ es la intersección de todos los superconjuntos ortogonalmente convexos de $K$ ; Ottmann, Soisalon-Soininen y Wood (1984) .
Definición conectada : La envoltura convexa ortogonal de $K$ es el superconjunto conexo ortogonalmente convexo más pequeño de $K$ ; Nicholl et al. (1983) .
Definición funcional : La envoltura convexa ortogonal de $K$ es la intersección de los conjuntos de ceros de todas las funciones ortogonalmente convexas no negativas que son $0$ en $K$ ; Matoušek y Plecháč (1998) .

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 abajo, las figuras segunda a cuarta muestran, respectivamente, la envoltura convexa ortogonal máxima, la conectada y la funcional del conjunto de puntos. Como se puede observar, la envoltura convexa ortogonal es un polígono con algunos "bordes" degenerados, es decir, cadenas poligonales alternas ortogonalmente convexas con ángulo interior $90^{\circ }$ conectar vértices extremos.

Envolvente convexa ortogonal clásica

La envoltura convexa ortogonal clásica se puede definir de forma equivalente como el superconjunto ortogonalmente convexo más pequeño de un conjunto. $K\subset \mathbb {R} ^{2}$ , por analogía con la siguiente definición de la envoltura convexa: la envoltura convexa de $K$ es el superconjunto convexo más pequeño de $K$ La envoltura convexa ortogonal clásica puede estar desconectada. Si un conjunto de puntos no tiene ningún par de puntos sobre 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 $x\in \mathbb {R} ^{d}$ está en el interior de la envoltura convexa de un conjunto de puntos $K\subset \mathbb {R} ^{d}$ si, y solo si, ya está en la envoltura convexa de $d+1$ o menos puntos de $K$ Esta propiedad también es válida para las envolturas convexas ortogonales clásicas.

Envolvente convexa ortogonal conectada

Por definición, la envoltura convexa ortogonal conexa siempre es conexa. Sin embargo, no es única. Consideremos, por ejemplo, un par de puntos en el plano que no se encuentran sobre una línea horizontal ni vertical. La envoltura convexa ortogonal conexa de dichos puntos es una cadena poligonal alternante ortogonalmente convexa con ángulo interior $90^{\circ }$ conectando los puntos. Cualquier cadena poligonal de este tipo tiene la misma longitud, por lo que existen infinitas envolturas convexas ortogonales conectadas para el conjunto de puntos.

Para conjuntos de puntos en el plano, la envoltura convexa ortogonal conectada 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 $K\subset \mathbb {R} ^{2}$ está conectado, entonces es igual a la envoltura convexa ortogonal conectada de $K$ . Si este no es el caso, entonces hay infinitos envolventes convexas ortogonales conectadas para $K$ y cada uno se puede obtener uniendo los componentes conectados de la envoltura convexa ortogonal máxima de $K$ con cadenas poligonales alternas ortogonalmente convexas con ángulo interior $90^{\circ }$ .

Envolvente convexa ortogonal funcional

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 $f:\mathbb {R} ^{d}\rightarrow \mathbb {R}$ Se dice que una función es 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.

Algoritmos

Varios autores han estudiado algoritmos para la construcción de 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 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 .

Conceptos relacionados

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, la extensión ajustada de un espacio métrico finito está estrechamente relacionada con la envoltura convexa ortogonal. Si un conjunto finito de puntos en el plano tiene una envoltura convexa ortogonal conectada, dicha envoltura es la extensión ajustada para la distancia de Manhattan en el conjunto de puntos. Sin embargo, las envolturas ortogonales y las extensiones ajustadas difieren para conjuntos de puntos con envolturas ortogonales desconectadas, o en espacios L ^p de dimensiones superiores .

O'Rourke (1993) describe otros resultados sobre convexidad ortogonal y visibilidad ortogonal .

Referencias

Biswas, Arindam; Bhowmick, Partha; Sarkar, Moumita; Bhattacharya, Bhargab B. (2012), "Un algoritmo combinatorio de tiempo lineal para encontrar la envoltura ortogonal de un objeto en el plano digital" , Information Sciences , 216 : 176–195 , doi : 10.1016/j.ins.2012.05.029.
Fink, Eugene; Wood, Derick (1996), "Fundamentos de la convexidad de orientación restringida" (PDF) , Information Sciences , 92 ( 1–4 ): 175–196 , doi : 10.1016/0020-0255(96)00056-4 , S2CID 17771224 .
Fink, Eugene; Wood, Derick (1998), "Semiespacios generalizados en convexidad de orientación restringida" (PDF) , Journal of Geometry , 62 ( 1–2 ): 99–120 , doi : 10.1007/BF01237603 , S2CID 14709697 .
Karlsson, Rolf G.; Overmars, Mark H. (1988), "Algoritmos de línea de exploración en una cuadrícula", BIT , 28 (2): 227– 241, doi : 10.1007/BF01934088 , hdl : 1874/16270 , S2CID 32964283 .
Matoušek, J.; Plecháč, P. (1998), "Sobre envolventes funcionales separadamente convexas", Geometría discreta y computacional , 19 (1): 105– 130, doi : 10.1007/PL00009331.
Montuno, DY; Fournier, A. (1982), Hallando la envoltura convexa $x$ - $y$ de un conjunto de polígonos $x$ - $y$ , Informe técnico 148, Universidad de Toronto.
Nicholl, TM; Lee, DT ; Liao, YZ; Wong, CK (1983), "Sobre la envoltura convexa XY de un conjunto de polígonos XY", BIT , 23 (4): 456–471 , doi : 10.1007/BF01933620 , S2CID 10492640 .
O'Rourke, Joseph ( 1993), Geometría computacional en C , Cambridge University Press, págs. 107–109 .
Ottmann, T.; Soisalon-Soininen, E.; Wood, Derick (1984), "Sobre la definición y el cálculo de envolventes convexas rectilíneas", Information Sciences , 33 (3): 157–171 , doi : 10.1016/0020-0255(84)90025-2.
Rawlins, GJE (1987), Exploraciones en geometría de orientación restringida , tesis doctoral e informe técnico CS-87-57, Universidad de Waterloo..
Rawlins, GJE; Wood, Derick (1987), "Cálculo óptimo de envolventes convexas con orientación finita", Information and Computation , 72 (2): 150–166 , doi : 10.1016/0890-5401(87)90045-9.
Rawlins, GJE; Wood, Derick (1988), "Ortoconvexidad y sus generalizaciones", en Toussaint, Godfried T. (ed.), Morfología computacional , Elsevier, pp . 137–152 .