Polígono monocromático

En geometría , un polígono P en el plano se denomina monótono con respecto a una línea recta L , si toda 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 denomina 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 fines prácticos , esta definición puede extenderse para permitir casos en los 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 para 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 contorno en dos cadenas poligonales monótonas , de modo que al recorrer los vértices de cualquier cadena en su orden natural, sus coordenadas x aumentan o disminuyen monótonamente . De hecho, esta propiedad puede considerarse la definición de polígono monótono y le da 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 todas las líneas rectas es convexo.

Se conoce un algoritmo de tiempo lineal que 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 direcciones diferentes). ^{[ 3 ]}

Las consultas de puntos en polígonos con respecto a un polígono monótono pueden responderse en tiempo logarítmico después de un preprocesamiento en tiempo lineal (para encontrar los vértices más a la izquierda y más a la derecha). ^{[ 1 ]}

Un polígono monótono puede triangularse 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 dichos puntos. El recorrido bitónico de perímetro mínimo para un conjunto de puntos dado con respecto a una dirección fija puede hallarse en tiempo polinomial mediante programación dinámica . ^{[ 5 ]} Se demuestra fácilmente que dicho recorrido bitónico mínimo es un polígono simple: un par de aristas que se cruzan pueden sustituirse por un par más corto que no se cruce, conservando la bitonicidad del nuevo recorrido.

Un polígono simple se puede dividir 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 consiste en dividir un polígono en polígonos monótonos, y se puede realizar 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 ]} 

Dividir 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 de movimiento , dos polígonos monótonos que no se intersecan son separables mediante una única traslación (es decir, existe una traslación de un polígono tal que los dos se separan mediante una línea recta en diferentes semiplanos) y esta separación puede encontrarse en tiempo lineal. ^{[ 9 ]}

• 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 en coordenadas polares de los polígonos monótonos.