En geometría , un polígono P en el plano se llama monótono con respecto a una línea recta L , si cada línea ortogonal a L interseca P a lo sumo dos veces. [1]
De manera similar, una cadena poligonal C se llama monótona con respecto a una línea recta L , si cada línea ortogonal a L se cruza con C como máximo una vez.
Para muchos propósitos prácticos esta definición puede ser ampliado para que los casos cuando algunos bordes de P son ortogonales a L , y un polígono sencillo puede ser llamado monótona si un segmento de línea que conecta dos puntos en P y es ortogonal a L pertenece totalmente a P .
Siguiendo la terminología para funciones monótonas , la definición anterior describe polígonos estrictamente monótona con respecto a L . La parte "con respecto a" es necesaria para trazar la distinción estricta / no estricta: un polígono no estrictamente monótono con respecto a L es estrictamente monótono con respecto a una línea L 1 rotada desde L en un ángulo suficientemente pequeño.
Propiedades
Suponga que L coincide con el eje x . Luego, los vértices más a la izquierda y más a la derecha de un polígono monótono descomponen su límite en dos cadenas poligonales monótonas de modo que cuando los vértices de cualquier cadena se atraviesan en su orden natural, sus coordenadas X aumentan o disminuyen monótonamente . De hecho, esta propiedad puede tomarse para la definición de polígono monótono y le da al polígono su nombre.
Un polígono convexo es monótono con respecto a cualquier línea recta y un polígono que es monótono con respecto a cada línea recta es convexo.
Se sabe que un algoritmo de tiempo lineal informa todas las direcciones en las que un polígono simple dado es monótono. [2] Se generalizó informar todas las formas de descomponer un polígono simple en dos cadenas monótonas (posiblemente monótonas en diferentes direcciones). [3]
Las consultas de punto en polígono con respecto a un polígono monótono se pueden responder en tiempo logarítmico después del preprocesamiento de tiempo lineal (para encontrar los vértices más a la izquierda y más a la derecha). [1]
Un polígono monótono se puede triangular fácilmente en tiempo lineal. [4]
Para un conjunto dado de puntos en el plano, un recorrido bitónico es un polígono monótono que conecta los puntos. El recorrido bitónico del perímetro mínimo para un conjunto de puntos dado con respecto a una dirección fija se puede encontrar en tiempo polinómico usando programación dinámica . [5] Se muestra fácilmente que un recorrido bitónico mínimo es un polígono simple: un par de bordes que se cruzan se pueden reemplazar por un par más corto que no se cruza mientras se conserva la bitonicidad del nuevo recorrido.
Un polígono simple se puede cortar fácilmente en polígonos monótonos en un tiempo O ( n log n ). Sin embargo, dado que un triángulo es un polígono monótono, la triangulación de polígonos es de hecho cortar un polígono en monótonos, y se puede realizar para polígonos simples en un tiempo O ( n ). [ cita requerida ]
Cortar un polígono simple en el número mínimo de polígonos uniformemente monótonos (es decir, monótono con respecto a la misma línea) se puede realizar en tiempo polinómico. [6]
En el contexto de la planificación del movimiento , dos polígonos monótonos no intersectantes se pueden separar mediante una sola traslación (es decir, existe una traslación de un polígono de modo que los dos quedan separados por una línea recta en diferentes semiplanos) y esta separación se puede encontrar en tiempo lineal . [7]
Generalizaciones
Polígonos barribles
Un polígono se llama barrible , si una línea recta puede moverse continuamente sobre todo el polígono de tal manera que en cualquier momento su intersección con el área poligonal sea un conjunto convexo. Un polígono monótono se puede barrer con una línea que no cambia su orientación durante el barrido. Un polígono se puede barrer estrictamente si ninguna parte de su área se barre más de una vez. Ambos tipos de barrido se reconocen en tiempo cuadrático. [8]
3D
No existe una generalización sencilla y sencilla de la monotonicidad de los polígonos a dimensiones superiores.
En un enfoque de la monotonía conservado rasgo es la línea L . Un poliedro tridimensional se denomina débilmente monótono en la dirección L si todas las secciones transversales ortogonales a L son polígonos simples. Si las secciones transversales son convexas, entonces el poliedro se llama débilmente monótono en sentido convexo . [7] Ambos tipos pueden reconocerse en tiempo polinomial. [8]
En otro enfoque, el rasgo unidimensional conservado es la dirección ortogonal. Esto da lugar a la noción de terreno poliédrico en tres dimensiones: una superficie poliédrica con la propiedad de que cada línea vertical (es decir, paralela al eje Z) interseca la superficie como máximo en un punto o segmento.
Ver también
- Convexidad ortogonal , para polígonos que son monótonos simultáneamente con respecto a dos direcciones mutuamente ortogonales; también una generalización para cualquier número de direcciones fijas.
- Polígonos en forma de estrella , un análogo de coordenadas polares de polígonos monótonos
Referencias
- ↑ a b Preparata, Franco P .; Shamos, Michael Ian (1985), Geometría computacional - Introducción , Springer-Verlag , ISBN 0-387-96131-3, 1ª edición:; Segunda impresión, corregida y ampliada, 1988:; Traducción al ruso, 1989
- ^ Preparata, Franco P .; Supowit, Kenneth J. (1981), "Testing a simple polygon for monotonicity", Information Processing Letters , 12 (4): 161-164, doi : 10.1016 / 0020-0190 (81) 90091-0.
- ^ Rappaport, David; Rosenbloom, Arnold (1994), "Polígonos moldeables y calcinables", Geometría computacional , 4 (4): 219-233, doi : 10.1016 / 0925-7721 (94) 90020-5.
- ^ Fournier, A .; Montuno, DY (1984), "Triangulación de polígonos simples y problemas equivalentes", ACM Transactions on Graphics , 3 (2): 153–174, doi : 10.1145 / 357337.357341 , ISSN 0730-0301 , S2CID 33344266
- ^ Introducción a los algoritmos , 2ª ed., TH Cormen , CE Leiserson , R. Rivest y C. Stein , MIT Press , 2001. Problema 15-1, p. 364.
- ^ Liu, Robin (1988), "Sobre la descomposición de polígonos en partes uniformemente monótonas", Information Processing Letters , 27 (2): 85–89, doi : 10.1016 / 0020-0190 (88) 90097-X.
- ^ a b Toussaint, GT ; El Gindy, HA (1984), "Separación de dos polígonos monótonos en tiempo lineal", Robotica , 2 (4): 215-220, doi : 10.1017 / S0263574700008924.
- ^ a b Bose, Prosenjit ; van Kreveld, Marc (2005), "Generalizar la monotonicidad: sobre el reconocimiento de clases especiales de polígonos y poliedros calculando barridos agradables", International Journal of Computational Geometry & Applications , 15 (6): 591–608, doi : 10.1142 / S0218195905001877 , hdl : 1874/24150.