Envolvente ortogonalmente convexa

En geometría, un conjunto K ⊂ R^d se define como ortogonalmente convexo (o también de forma abreviada, ortoconvexo) si, para cada recta L paralela a uno de los vectores de la base canónica de coordenadas, la intersección de K con L está vacía, es un punto o es un único segmento. El término ortogonal se refiere a la base y a las coordenadas correspondientes de las coordenadas cartesianas en el espacio euclídeo, donde los diferentes vectores de la base son perpendiculares entre sí, así como los ejes correspondientes. A diferencia de las envolventes convexas ordinarias, un conjunto ortogonalmente convexo no es necesariamente conexo.

Archivo:Orthogonal-convex-hull.svg

La envolvente ortogonalmente convexa de un conjunto de puntos

La envolvente ortogonalmente convexa de un conjunto K ⊂ R^d es la intersección de todos los superconjuntos ortogonalmente convexos conexos 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 recta L, la intersección de K con L está vacía, es un punto o un solo segmento. La convexidad ortogonal restringe las rectas para las que se requiere que se cumpla esta propiedad, por lo que todo conjunto convexo es ortogonalmente convexo pero no viceversa. Por la misma razón, la propia envolvente ortogonalmente convexa es un subconjunto de la envolvente convexa del mismo conjunto de puntos. Un punto p pertenece a la envolvente ortogonalmente convexa de K si y solo si cada uno de los ortantes cerrados alineados con los ejes que tienen p como vértice, tienen una intersección no vacía con K.

La envolvente ortogonalmente convexa también se conoce como envolvente convexa rectilínea o, en dos dimensiones, envolvente convexa x-y.

Ejemplo

La figura muestra un conjunto de 16 puntos en el plano y la envolvente ortogonalmente convexa de estos puntos. Como se puede observar en la figura, la envolvente ortogonalmente convexa 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 envolvente ortogonalmente convexa son horizontales o verticales. En este ejemplo, la envolvente ortogonalmente convexa es conexa.

Definiciones alternativas

Archivo:Point set.svg

Un conjunto de seis puntos en el plano. La envolvente ortoconvexa clásica es el propio conjunto de puntos

Archivo:Maximal orthogonal convex hull.svg

La envolvente ortoconvexa máxima del conjunto de puntos de la figura superior. Está formada por el conjunto de puntos y el área coloreada

Archivo:Connected orthogonal convex hull.svg

Una envolvente ortoconvexa conexa del conjunto de puntos de la figura superior. Está formada por el conjunto de puntos, el área coloreada y las dos cadenas poligonales ortoconvexas

Archivo:Functional D-convex Hull.svg

La envolvente ortoconvexa funcional del conjunto de puntos de la figura superior. Está formada por el conjunto de puntos, el área coloreada y los cuatro segmentos de recta

A diferencia de lo que sucede con el concepto de convexidad clásico, donde existen varias definiciones equivalentes de la envolvente convexa, las definiciones de la envolvente ortogonalmente convexa, hechas por analogía con las de la envolvente convexa, resultan en diferentes objetos geométricos. Hasta el momento, los investigadores han explorado las siguientes cuatro definiciones de la envolvente ortogonalmente convexa de un conjunto $K\subset {ℝ}^d$:

1. 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.
2. Definición clásica: la envolvente ortogonalmente convexa de $K$ es la intersección de todos los subconjuntos ortogonalmente convexos de $K$; Ottmann, Soisalon-Soininen y Wood (1984).
3. Definición conexa: la envolvente ortogonalmente convexa de $K$ es el superconjunto conexo ortogonalmente convexo más pequeño de $K$; Nicholl et al. (1983).
4. Definición funcional: la envolvente ortogonalmente convexa de $K$ es la intersección de las raíces 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 envolvente ortogonalmente convexa clásica del conjunto de puntos es el propio conjunto de puntos. De arriba abajo, las figuras segunda a cuarta muestran, respectivamente, la envolvente ortogonalmente convexa máxima, la conexa y la funcional del conjunto de puntos. Como se puede observar, la envolvente ortogonalmente convexa es un polígono con algunas aristas degeneradas, es decir, cadenas poligonales alternantes ortogonalmente convexas con un ángulo interior de $90^{\circ }$ que conecta los vértices extremos.

Envolvente ortogonalmente convexa clásica

La envolvente ortogonalmente convexa clásica puede definirse de forma equivalente como el superconjunto ortogonalmente convexo más pequeño de un conjunto $K\subset {ℝ}^2$, por analogía con la siguiente definición de envolvente convexa: la envolvente convexa de $K$ es el superconjunto convexo más pequeño de $K$. La envolvente ortogonalmente convexa clásica podría ser disociada. 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 envolvente ortogonalmente convexa clásica de dicho conjunto de puntos es igual al propio conjunto de puntos.

Una propiedad bien conocida de las envolventes convexas se deriva del teorema de Carathéodory: un punto $x\in {ℝ}^d$ se encuentra en el interior de la envolvente convexa de un conjunto de puntos $K\subset {ℝ}^d$ si, y solo si, ya se encuentra en la envolvente convexa de $d+1$ o en menos puntos de $K$. Esta propiedad también es válida para las envolventes convexas ortogonales clásicas.

Envolvente ortogonalmente convexa conexa

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

Para conjuntos de puntos en el plano, la envolvente ortogonalmente convexa conexa se puede obtener fácilmente a partir de la envolvente ortogonalmente convexa máxima. Si la envolvente ortogonalmente convexa máxima de un conjunto de puntos $K\subset {ℝ}^2$ es conexa, entonces es igual a la envolvente ortogonalmente convexa conexa de $K$. De no ser así, entonces existen infinitas envolventes convexas ortogonales conexas para $K$, y cada una puede se obtiene uniendo las componentes conexas de la envolvente ortogonalmente convexa máxima de $K$ con cadenas poligonales alternas ortogonalmente convexas con ángulo interior $90^{\circ }$.

Envolvente ortogonalmente convexa funcional

La envolvente ortogonalmente convexa funcional no se define mediante propiedades de conjuntos, sino de funciones sobre conjuntos. Es decir, restringe el concepto de función convexa de la siguiente manera: una función $f:{ℝ}^d\to ℝ$ se denomina 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 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 ortogonalmente convexa 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 entera 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 rectas con una pendiente de un conjunto finito de pendientes deben intersecar a K en subconjuntos conexos (véanse, por ejemplo, Rawlins (1987), Rawlins y Wood (1987), Fink o Wood (1996)).

Además, el valor la amplitud estrecha de un conjunto finito de puntos en un espacio métrico está estrechamente relacionada con la envolvente ortogonalmente convexa. Si un conjunto de puntos finito en el plano tiene una envolvente ortogonalmente convexa conexa, dicha envolvente es la envolvente estrecha según la geometría del taxista en el conjunto de puntos. Sin embargo, las envolventes ortogonales y las envolventes estrechas difieren para conjuntos de puntos con envolventes ortogonales desconectadas o en espacios L^p de mayor dimensión.

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

Referencias

• Biswas, Arindam; Bhowmick, Partha; Sarkar, Moumita; Bhattacharya, Bhargab B. (2012), «A Linear-time Combinatorial Algorithm to Find the Orthogonal Hull of an Object on the Digital Plane», Information Sciences 216: 176-195, doi:10.1016/j.ins.2012.05.029 ..
• Fink, Eugene; Wood, Derick (1996), «Fundamentals of restricted-orientation convexity», Information Sciences 92 (1–4): 175-196, S2CID 17771224, doi:10.1016/0020-0255(96)00056-4 ..
• Fink, Eugene; Wood, Derick (1998), «Generalized halfspaces in restricted-orientation convexity», Journal of Geometry 62 (1–2): 99-120, S2CID 14709697, doi:10.1007/BF01237603 ..
• Karlsson, Rolf G.; Overmars, Mark H. (1988), «Scanline algorithms on a grid», BIT 28 (2): 227-241, S2CID 32964283, doi:10.1007/BF01934088, hdl:1874/16270 ..
• Matoušek, J.; Plecháč, P. (1998), «On Functional Separately Convex Hulls», Discrete & Computational Geometry 19 (1): 105-130, doi:10.1007/PL00009331 ..
• Montuno, D. Y.; Fournier, A. (1982), Finding the x-y convex hull of a set of x-y polygons, Technical Report 148, University of Toronto ..
• Nicholl, T. M.; Lee, D. T.; Liao, Y. Z.; Wong, C. K. (1983), «On the X-Y convex hull of a set of X-Y polygons», BIT 23 (4): 456-471, S2CID 10492640, doi:10.1007/BF01933620 ..
• O'Rourke, Joseph (1993), Computational Geometry in C, Cambridge University Press, pp. 107-109 ..
• Ottmann, T.; Soisalon-Soininen, E.; Wood, Derick (1984), «On the definition and computation of rectilinear convex hulls», Information Sciences 33 (3): 157-171, doi:10.1016/0020-0255(84)90025-2 ..
• Rawlins, G. J. E. (1987), Explorations in Restricted-Orientation Geometry, Ph.D. thesis and Tech. Rep. CS-87-57, University of Waterloo ..
• Rawlins, G. J. E.; Wood, Derick (1987), «Optimal computation of finitely oriented convex hulls», Information and Computation 72 (2): 150-166, doi:10.1016/0890-5401(87)90045-9 ..
• Rawlins, G. J. E.; Wood, Derick (1988), «Ortho-convexity and its generalizations», en Toussaint, Godfried T., ed., Computational Morphology, Elsevier, pp. 137-152 ..