Envolvente convexa relativa

La región azul es la envoltura convexa relativa del conjunto finito de puntos en el polígono simple amarillo.

En geometría discreta y geometría computacional , la envoltura convexa relativa o envoltura convexa geodésica es un análogo de la envoltura convexa para los puntos dentro de un polígono simple o una curva cerrada simple rectificable .

Definición

Sea un polígono simple o una curva cerrada simple rectificable, y sea cualquier conjunto encerrado por . Una geodésica entre dos puntos en es un camino más corto que conecta esos dos puntos y que permanece completamente dentro de . Se dice que un subconjunto de los puntos dentro de , es relativamente convexo, geodésicamente convexo o -convexo si, para cada dos puntos de , la geodésica entre ellos en permanece dentro de . Entonces, la envoltura convexa relativa de se puede definir como la intersección de todos los conjuntos relativamente convexos que contienen . ^[1] ${\displaystyle P}$ ${\displaystyle X}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle K}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle K}$ ${\displaystyle P}$ ${\displaystyle K}$ ${\displaystyle X}$ ${\displaystyle X}$

De manera equivalente, la envoltura convexa relativa es el polígono débilmente simple de perímetro mínimo que encierra . Esta fue la formulación original de las envolturas convexas relativas, por Sklansky, Chazin y Hansen (1972). ^[2] Sin embargo, esta definición se complica por la necesidad de utilizar polígonos débilmente simples (intuitivamente, polígonos en los que el límite del polígono puede tocarse o superponerse a sí mismo pero no cruzarse a sí mismo) en lugar de polígonos simples cuando está desconectado y sus componentes no son todos visibles entre sí. ${\displaystyle P}$ ${\displaystyle X}$ ${\displaystyle X}$

Casos especiales

Conjuntos finitos de puntos

Toussaint (1986), quien proporcionó un algoritmo eficiente para la construcción de la envoltura convexa relativa para conjuntos finitos de puntos dentro de un polígono simple . ^[3] Con mejoras posteriores en los límites de tiempo para dos subrutinas, encontrar caminos más cortos entre puntos de consulta en un polígono, ^[4] y triangulación de polígonos , ^[5] este algoritmo toma tiempo en una entrada con puntos en un polígono con vértices. ^[4] También se puede mantener dinámicamente en tiempo sublineal por actualización. ^[6] ${\displaystyle O(p+n\log(p+n))}$ ${\displaystyle n}$ ${\displaystyle p}$

La envoltura convexa relativa de un conjunto finito de puntos es siempre un polígono débilmente simple , pero en realidad podría no ser un polígono simple, porque partes de él pueden estar conectadas entre sí por segmentos de línea o caminos poligonales en lugar de por regiones de área distinta de cero.

Polígonos simples

Para las envolturas convexas relativas de polígonos simples, se puede utilizar una definición alternativa pero equivalente de convexidad. Un polígono simple dentro de otro polígono simple es relativamente convexo o -convexo si cada segmento de línea contenido en que conecta dos puntos de se encuentra dentro de . La envoltura convexa relativa de un polígono simple dentro de se puede definir como la intersección de todos los polígonos -convexos que contienen , como el polígono -convexo más pequeño que contiene , o como el polígono simple de perímetro mínimo que contiene y está contenido por . ^[1] ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle Q}$

Klette (2010) generaliza algoritmos de tiempo lineal para la envoltura convexa de un polígono simple a la envoltura convexa relativa de un polígono simple dentro de otro. Sin embargo, el algoritmo generalizado resultante no es de tiempo lineal: su complejidad temporal depende de la profundidad de anidación de ciertas características de un polígono dentro de otro. En este caso, la envoltura convexa relativa es en sí misma un polígono simple. ^[1] Se conocen algoritmos de tiempo lineal alternativos basados ​​en la planificación de trayectorias . ^[7]

También se puede dar una definición similar para la envoltura convexa relativa de dos polígonos simples disjuntos. Este tipo de envoltura se puede utilizar en algoritmos para comprobar si los dos polígonos se pueden separar en semiplanos disjuntos mediante un movimiento lineal continuo ^[8] , y en estructuras de datos para la detección de colisiones de polígonos en movimiento ^[9] .

Dimensiones superiores

La definición de envolturas convexas relativas basadas en un recinto mínimo no se extiende a dimensiones superiores, porque (incluso sin estar rodeado por una forma exterior) el recinto de área superficial mínima de un conjunto no convexo no es generalmente convexo. ^[7] Sin embargo, para la envoltura convexa relativa de un conjunto conectado dentro de otro conjunto, se puede utilizar una definición similar a la de los polígonos simples. En este caso, un conjunto relativamente convexo se puede definir nuevamente como un subconjunto del conjunto exterior dado que contiene todos los segmentos de línea en el conjunto exterior entre pares de sus puntos. La envoltura convexa relativa se puede definir como la intersección de todos los conjuntos relativamente convexos que contienen el conjunto interior. ^[10]

Referencias

1. Klette, Gisela (noviembre de 2010), "Un algoritmo recursivo para calcular la envoltura convexa relativa", 25.ª Conferencia internacional de computación de imágenes y visión de Nueva Zelanda , IEEE, págs. 1–7, doi :10.1109/ivcnz.2010.6148857, ISBN 978-1-4244-9631-0, Número de identificación del sujeto  17854252
2. Sklansky, Jack; Chazin, Robert L.; Hansen, Bruce J. (1972), "Polígonos de perímetro mínimo de siluetas digitalizadas", IEEE Transactions on Computers , C-21 (3): 260–268, doi :10.1109/tc.1972.5008948, S2CID  6818423
3. Toussaint, Godfried (1986), "Un algoritmo óptimo para calcular la envoltura convexa relativa de un conjunto de puntos en un polígono", Actas de EURASIP, Procesamiento de señales III: Teorías y aplicaciones, Parte 2 , North-Holland, págs. 853–856
4. Guibas, Leonidas J. ; Hershberger, John (1989), "Consultas de ruta más corta óptima en un polígono simple", Journal of Computer and System Sciences , 39 (2): 126–152, doi : 10.1016/0022-0000(89)90041-X , MR  1024124
5. Chazelle, Bernard (1991), "Triangulación de un polígono simple en tiempo lineal", Geometría discreta y computacional , 6 (3): 485–524, doi : 10.1007/BF02574703
6. Oh, Eunjin; Ahn, Hee-Kap (2017), "Cascos convexos geodésicos dinámicos en polígonos simples dinámicos", 33.° Simposio Internacional sobre Geometría Computacional (SoCG 2017) , LIPIcs, vol. 77, Schloss Dagstuhl, págs. 51:1–51:15, doi : 10.4230/LIPIcs.SoCG.2017.51 , MR  3685723
7. Williams, Jason; Rossignac, Jarek (2005), "Tightening: curvature-limiting morphological simplification", en Kobbelt, Leif; Shapiro, Vadim (eds.), Actas del Décimo Simposio ACM sobre Modelado Físico y Sólido 2005, Cambridge, Massachusetts, EE. UU., 13-15 de junio de 2005 , ACM, págs. 107-112, doi :10.1145/1060244.1060257, hdl :1853/3736, S2CID  15514388
8. Toussaint, Godfried (1989), "Sobre la separación de dos polígonos simples mediante una sola traslación", Geometría discreta y computacional , 4 (3): 265–278, doi : 10.1007/BF02187729 , MR  0988749
9. Basch, Julien; Erickson, Jeff; Guibas, Leonidas J .; Hershberger, John ; Zhang, Li (2004), "Detección de colisiones cinéticas entre dos polígonos simples", Computational Geometry , 27 (3): 211–235, doi :10.1016/j.comgeo.2003.11.001, MR  2039172, S2CID  300999
10. Sloboda, Fridrich; Za'ko, Bedrich (2001), "Sobre la aproximación de superficies de Jordan en 3D", en Bertrand, G.; Imiya, A.; Klette, R. (eds.), Geometría digital y de imágenes: conferencias avanzadas , Lecture Notes in Computer Science, vol. 2243, Springer, págs. 365–386, doi :10.1007/3-540-45576-0_22, ISBN 978-3-540-43079-7