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 el límite de P como máximo 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 interseca a C como máximo una vez.
Para muchos propósitos prácticos, esta definición puede extenderse para permitir casos en que algunos bordes de P son ortogonales a L , y un polígono simple puede llamarse monótono si un segmento de línea que conecta dos puntos en P y es ortogonal a L se encuentra completamente en P.
Siguiendo la terminología de funciones monótonas , la definición anterior describe polígonos estrictamente monótonos con respecto a L.
Supongamos que L coincide con el eje x . Entonces, 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 recorren en su orden natural, sus coordenadas X aumentan o disminuyen monótonamente . De hecho, esta propiedad puede tomarse como 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 toda 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ó para 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 puntos en polígonos 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 perimetral mínimo para un conjunto de puntos dado con respecto a una dirección fija se puede encontrar en tiempo polinomial utilizando programación dinámica . [5] Se demuestra fácilmente que un recorrido bitónico mínimo de este tipo es un polígono simple: un par de aristas que se cruzan se puede reemplazar por un par más corto que no se cruza mientras se preserva la bitonicidad del nuevo recorrido.
Un polígono simple puede cortarse fácilmente en polígonos monótonos en 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 polígonos monótonos, y puede realizarse para polígonos simples en tiempo O ( n ) con un algoritmo complejo. [6] También se conoce un algoritmo aleatorio más simple con tiempo esperado lineal. [7]
El corte de un polígono simple en el número mínimo de polígonos uniformemente monótonos (es decir, monótonos con respecto a la misma línea) se puede realizar en tiempo polinomial. [8]
En el contexto de la planificación del movimiento , dos polígonos monótonos que no se intersecan son separables por una única traslación (es decir, existe una traslación de un polígono tal que los dos quedan separados por una línea recta en semiplanos diferentes) y esta separación se puede encontrar en tiempo lineal. [9]
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 es barrible por una línea que no cambia su orientación durante el barrido. Un polígono es estrictamente barrible si ninguna porción de su área se barre más de una vez. Ambos tipos de barribilidad se reconocen en tiempo cuadrático. [10]
No existe una generalización única y directa de la monotonía de los polígonos a dimensiones superiores.
En un enfoque, el rasgo de monotonía preservado 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 denomina débilmente monótono en sentido convexo . [9] Ambos tipos pueden reconocerse en tiempo polinomial. [10]
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.