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 es vacía, un punto o un solo segmento . El término "ortogonal" se refiere a las bases cartesianas correspondientes y a las coordenadas en el espacio euclidiano , donde diferentes vectores de base son perpendiculares , así como las líneas correspondientes. A diferencia de los conjuntos convexos ordinarios , un conjunto ortogonalmente convexo no es necesariamente conexo .
El casco convexo 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 recta 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 cuales se requiere que se cumpla esta propiedad, por lo que todo conjunto convexo es ortogonalmente convexo, pero no al revés. Por la misma razón, la propia carcasa convexa ortogonal es un subconjunto de la carcasa convexa del mismo conjunto de puntos. Un punto p pertenece al casco convexo ortogonal de K si y solo si cada uno de los orantes alineados con el eje cerrado que tiene p como vértice tiene una intersección no vacía con K.
La carcasa convexa ortogonal también se conoce como carcasa convexa rectilínea o, en dos dimensiones , carcasa convexa x - y .
La figura muestra un conjunto de 16 puntos en el plano y el casco convexo ortogonal de estos puntos. Como se puede ver en la figura, el casco convexo ortogonal es un polígono con algunos bordes degenerados que conectan vértices extremos en cada dirección de coordenadas. Para un conjunto de puntos discretos como este, todos los bordes del casco convexos ortogonales son horizontales o verticales. En este ejemplo, el casco convexo ortogonal está conectado.
A diferencia de la convexidad clásica, donde existen varias definiciones equivalentes de casco convexo, las definiciones de casco convexo ortogonal hechas por analogía con las de casco convexo dan como resultado objetos geométricos diferentes. Hasta ahora, los investigadores han explorado las siguientes cuatro definiciones de casco convexo ortogonal de un conjunto :
En las figuras de la derecha, la figura superior muestra un conjunto de seis puntos en el plano. El casco convexo ortogonal clásico del conjunto de puntos es el propio conjunto de puntos. De arriba a abajo, las figuras segunda a cuarta muestran respectivamente el casco convexo ortogonal máximo, conectado y funcional del conjunto de puntos. Como puede verse, la carcasa convexa ortogonal es un polígono con algunos "bordes" degenerados, es decir, cadenas poligonales alternas ortogonalmente convexas con un ángulo interior que conecta los vértices extremos.
La casco convexo ortogonal clásico se puede definir de manera equivalente como el superconjunto ortogonalmente convexo más pequeño de un conjunto , por analogía con la siguiente definición de casco convexo: el casco convexo de es el superconjunto convexo más pequeño de . El casco convexo ortogonal clásico podría estar desconectado. Si un conjunto de puntos no tiene un par de puntos en una línea paralela a uno de los vectores de base estándar, el casco convexo ortogonal clásico de dicho conjunto de puntos es igual al propio conjunto de puntos.
Una propiedad bien conocida de las cáscaras convexas se deriva del teorema de Carathéodory : un punto está en el interior de la cáscara convexa de un conjunto de puntos si, y sólo si, ya está en la cáscara convexa de o menos puntos de . Esta propiedad también es válida para cascos convexos ortogonales clásicos.
Por definición, el casco convexo ortogonal conectado siempre está conexo. Sin embargo, no es único. Consideremos, por ejemplo, un par de puntos en el plano que no se encuentran en una línea horizontal o vertical. El casco convexo ortogonal conectado de dichos 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 infinitos cascos convexos ortogonales conectados para el conjunto de puntos.
Para conjuntos de puntos en el plano, el casco convexo ortogonal conectado se puede obtener fácilmente a partir del casco convexo ortogonal máximo. Si el casco convexo ortogonal máximo de un conjunto de puntos está conectado, entonces es igual al casco convexo ortogonal conectado de . Si este no es el caso, entonces hay infinitos cascos convexos ortogonales conectados para , y cada uno se puede obtener uniendo los componentes conectados del casco convexo ortogonal máximo de con cadenas poligonales alternas ortogonalmente convexas con ángulo interior .
El casco convexo 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 de base estándar distinto de cero es una función convexa.
Varios autores han estudiado algoritmos para la construcción de cascos convexos ortogonales: Montuno & Fournier (1982); Nicholl y cols. (1983); Ottmann, Soisalon-Soininen y Wood (1984); Karlsson y Overmars (1988). Según los resultados de estos autores, el casco convexo ortogonal de n puntos en el plano puede construirse en el tiempo O ( n log n ) , o posiblemente más rápido utilizando estructuras de datos de búsqueda de números 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 cortar a K en subconjuntos conectados; véase, por ejemplo, Rawlins (1987), Rawlins y Wood (1987, 1988) o Fink y Wood (1996, 1998).
Además, la estrecha extensión de un espacio métrico finito está estrechamente relacionada con el casco convexo ortogonal. Si un punto finito establecido en el plano tiene un casco convexo ortogonal conectado, ese casco es el tramo estrecho para la distancia de Manhattan en el punto establecido. Sin embargo, los cascos ortogonales y los tramos estrechos difieren para conjuntos de puntos con cascos ortogonales desconectados o en espacios L p de dimensiones superiores .
O'Rourke (1993) describe varios otros resultados sobre la convexidad ortogonal y la visibilidad ortogonal .
