Cobertura poligonal

Conjunto de formas primitivas cuya unión da como resultado un polígono

En geometría , una cobertura de un polígono es un conjunto de unidades primitivas (por ejemplo, cuadrados) cuya unión es igual al polígono. Un problema de cobertura de polígono es un problema de encontrar una cobertura con un número menor de unidades para un polígono dado. Esta es una clase importante de problemas en geometría computacional . Hay muchos problemas de cobertura de polígonos diferentes, según el tipo de polígono que se esté cubriendo. Un ejemplo de problema de cobertura de polígono es: dado un polígono rectilíneo , encuentre el conjunto más pequeño de cuadrados cuya unión sea igual al polígono.

En algunos escenarios, no es necesario cubrir todo el polígono, sino solo sus bordes (esto se denomina cobertura de bordes de polígono ) o sus vértices (esto se denomina cobertura de vértices de polígono ).

En un problema de recubrimiento , las unidades del recubrimiento pueden superponerse, siempre que su unión sea exactamente igual al polígono de destino. Esto contrasta con un problema de empaquetamiento , en el que las unidades deben estar disjuntas y su unión puede ser más pequeña que el polígono de destino, y con un problema de partición de polígonos , en el que las unidades deben estar disjuntas y su unión debe ser igual al polígono de destino.

Un problema de cobertura de polígonos es un caso especial del problema de cobertura de conjuntos . En general, el problema de encontrar la cobertura de conjuntos más pequeña es NP-completo, pero para clases especiales de polígonos, la cobertura de polígonos más pequeña se puede encontrar en tiempo polinomial.

Una cubierta de un polígono P es una colección de unidades máximas, posiblemente superpuestas, cuya unión es igual a P.

Una cobertura mínima es una cobertura que no contiene ninguna otra cobertura (es decir, es un mínimo local).

Una cobertura mínima es una cobertura con el menor número de unidades (es decir, un mínimo global). Toda cobertura mínima es mínima, pero no al revés.

Cubriendo un polígono rectilíneo con cuadrados

Un polígono rectilíneo siempre puede cubrirse con un número finito de vértices del polígono. ^[1] El algoritmo utiliza un enfoque de optimización local: construye la cobertura seleccionando iterativamente los cuadrados máximos que son esenciales para la cobertura (es decir, que contienen puntos descubiertos que no están cubiertos por otros cuadrados máximos) y luego eliminando del polígono los puntos que se vuelven innecesarios (es decir, innecesarios para soportar cuadrados futuros). Aquí hay un pseudocódigo simplificado del algoritmo:

• Mientras el polígono P no esté vacío:
  • Seleccione un cuadrado continuador s en P .
  • Si el balcón de s aún no está cubierto, entonces agregue s a la cubierta.
  • Quitar el balcón de s de P.
  • Si lo que queda de s es un continuador de un solo botón, entonces retire de P un cierto rectángulo adyacente al botón, teniendo cuidado de dejar una distancia de seguridad suficiente para futuros cuadrados.

Para los polígonos que pueden contener agujeros, encontrar un mínimo de dicha cobertura es NP-difícil . ^[2] Esta marcada diferencia entre polígonos sin agujeros y polígonos generales se puede explicar intuitivamente basándose en la siguiente analogía entre los cuadrados máximos en un polígono rectilíneo y los nodos en un gráfico no dirigido: ^[1]

• Algunos cuadrados máximos tienen una intersección continua con el límite del polígono; cuando se eliminan, el polígono restante permanece conectado. Estos cuadrados se denominan "continuadores" y son análogos a los nodos hoja (nodos con una sola arista) que se pueden eliminar sin desconectar el grafo.
• Otros cuadrados máximos son "separadores": cuando se eliminan, el polígono se divide en dos polígonos desconectados. Son análogos a los nodos con dos o más aristas que, al eliminarse, dejan un resto desconectado.

En un polígono rectilíneo sin agujeros, todos los cuadrados máximos son continuadores o separadores; por lo tanto, un polígono de este tipo es análogo a un grafo de árbol . Un polígono general es análogo a un grafo general. Al igual que el problema de cobertura de vértices es polinómico para grafos de árbol pero NP-difícil para grafos generales, el problema de cobertura de cuadrados es lineal para polígonos sin agujeros pero NP-difícil para polígonos generales.

Es posible utilizar el algoritmo lineal para obtener una aproximación 2; es decir, una cobertura con como máximo 2 cuadrados opt , donde opt es el número de cuadrados en una cobertura mínima: ^[3]

• Para cada agujero, encuentre un cuadrado s que conecte el agujero con el límite externo.
• Recorta s del polígono y luego pega dos copias superpuestas de s (ver figura). El polígono resultante no es plano, pero sigue siendo bidimensional y ahora no tiene agujeros.
• Ahora utilice el algoritmo original para encontrar una cobertura mínima.

El número de cuadrados en la cubierta resultante es como máximo opt + holes , donde holes es el número de agujeros. Es posible demostrar que opt ≥ holes . Por lo tanto, el número de cuadrados en la cubierta es como máximo 2 opt .

Cubriendo un polígono rectilíneo con rectángulos

En el caso de polígonos rectilíneos generales, el problema de encontrar una cobertura mínima de rectángulos es NP-difícil, incluso cuando el polígono de destino no tiene agujeros. ^[4] Se han sugerido varias soluciones parciales para este problema:

1. En polígonos ortogonalmente convexos , el número de rectángulos en una cobertura mínima es igual al número de bloques en un antirectángulo, y este hecho se puede utilizar para construir un algoritmo de tiempo polinomial para encontrar una cobertura mínima por rectángulos. ^[5]
2. Incluso cuando el polígono objetivo es sólo medio ortogonalmente convexo (es decir, sólo en la dirección y ), se puede encontrar una cobertura mínima por rectángulos en el tiempo O( n ² ), donde n es el número de vértices del polígono. ^[6]
3. Se presenta un algoritmo de aproximación que da buenos resultados empíricos con datos de la vida real. ^[7]
4. Para polígonos rectilíneos que pueden contener agujeros, existe un algoritmo de aproximación de factor O( √ log n ). ^[8]

Recubrimiento de un polígono rectilíneo con polígonos ortogonalmente convexos

Para un polígono rectilíneo que es semiortogonalmente convexo (es decir, solo en la dirección x ), se puede encontrar un recubrimiento mínimo por polígonos ortogonalmente convexos en tiempo O( n ^2), donde n es el número de vértices del polígono. Lo mismo es cierto para un recubrimiento por polígonos rectilíneos en estrella . ^[9]

El número de componentes ortogonalmente convexos en un recubrimiento mínimo se puede encontrar, en algunos casos, sin encontrar el recubrimiento mismo, en el tiempo O( n ). ^[10]

Cubriendo un polígono rectilíneo con polígonos estrellados

Un polígono estrellado rectilíneo es un polígono P que contiene un punto p , tal que para cada punto q en P , hay un polígono ortogonalmente convexo que contiene p y q .

El problema de cubrir un polígono con polígonos estrellados es una variante del problema de la galería de arte .

El gráfico de visibilidad para el problema de cubrir mínimamente polígonos rectilíneos sin agujeros con polígonos en estrella es un gráfico perfecto . Esta propiedad de perfección implica un algoritmo polinomial para encontrar una cobertura mínima de cualquier polígono rectilíneo con polígonos en estrella rectilíneos. ^[11]

Cubrir un polígono sin ángulos agudos con cuadrados o rectángulos

La clase más general de polígonos para los que se pueden encontrar recubrimientos por cuadrados o rectángulos es la clase de polígonos sin ángulos agudos interiores. Esto se debe a que un ángulo agudo no puede ser cubierto por un número finito de rectángulos. Este problema es NP-hard, pero existen varios algoritmos de aproximación. ^[12]

Recubrimiento de un polígono con rectángulos de una familia finita

En algunos casos, un polígono debe cubrirse no con rectángulos arbitrarios sino con rectángulos de una familia finita. ^[13]

Cubriendo un polígono con triángulos

Encontrar el conjunto más pequeño de triángulos que cubren un polígono dado es una tarea NP-difícil. También es difícil de aproximar: cualquier algoritmo de tiempo polinómico podría encontrar una cobertura con un tamaño de (1 + 1/19151) veces la cobertura mínima. ^[14]

Si el polígono está en posición general (es decir, no hay dos aristas colineales), entonces cada triángulo puede cubrir como máximo 3 aristas del polígono. Por lo tanto, cada triangulación de polígono es una aproximación 3-aproximada.

Si la cobertura está restringida a triángulos cuyos vértices son vértices del polígono (es decir, no se permiten puntos de Steiner ), entonces el problema es NP-completo.

Si no se permiten puntos de Steiner y el polígono está en posición general (es decir, no hay dos bordes colineales), entonces cada recubrimiento mínimo sin puntos de Steiner también es una partición mínima del polígono en triángulos (es decir, los triángulos en el recubrimiento mínimo no se superponen). ^[14] Por lo tanto, el problema de recubrimiento mínimo es idéntico al problema de triangulación de polígonos, que se puede resolver en tiempo O( n log n ). Nótese que si descartamos el supuesto de posición general, hay polígonos en los que los triángulos en el recubrimiento óptimo se superponen. Pensemos en la Estrella de David , por ejemplo.

El problema de cubrir sólo el límite de un polígono con triángulos es NP-completo, pero existe una aproximación 2 eficiente. ^[14]

Cubrir un polígono con polígonos convexos

Cubrir un polígono (que puede contener agujeros) con polígonos convexos es NP-difícil. ^[15] También se ha demostrado que es -completo. ^[16] Existe un algoritmo de aproximación O(log n ). ^[17] ${\displaystyle \exists \mathbb {R} }$

Cubrir un polígono con polígonos convexos es NP-difícil incluso cuando el polígono objetivo no tiene agujeros . ^[4] También es APX-difícil , ^[17] pero hay un algoritmo de 6 aproximaciones para el caso sin agujeros. ^[18] El problema es NP-completo cuando el cubrimiento no debe introducir nuevos vértices (es decir, no se permiten puntos de Steiner ). ^[14]

Cubriendo un polígono con polígonos estrellados

Cubrir un polígono simple con polígonos estrellados es -completo , como lo es la versión en la que un punto en el núcleo de cada estrella debe estar contenido en un borde del polígono. ^[19] ${\displaystyle \exists \mathbb {R} }$

Cubrir un conjunto de puntos con cuadrados idénticos

Dado un conjunto S de puntos en el plano y un conjunto de cuadrados idénticos, el objetivo es encontrar el menor número de cuadrados que puedan cubrir todos los puntos en S.

Supongamos que, para cada punto p en S , ponemos un cuadrado centrado en p . Sea G _S el gráfico de intersección de estos cuadrados. Nótese que dos puntos en S pueden ser cubiertos por un solo cuadrado, si y sólo si los dos cuadrados centrados en ellos se superponen. Por lo tanto, una cobertura de cuadrados de los puntos en S es equivalente a una cobertura de clique de G _S . Encontrar una cobertura de cuadrados más pequeña de S es NP-hard; la prueba es por reducción de 3SAT . ^[20]

Otras combinaciones

Cubrir un polígono (que puede contener agujeros) con polígonos espirales es NP-difícil. ^[15]

También se ha estudiado el cubrimiento de un polígono con pseudotriángulos .

Información adicional se puede encontrar en. ^[21]

Véase también

• Problemas de cobertura
• Problema de la galería de arte
• Mosaico

Referencias

1. Bar-Yehuda, R.; Ben-Hanoch, E. (1996). "Un algoritmo de tiempo lineal para cubrir polígonos simples con rectángulos similares". Revista internacional de geometría computacional y aplicaciones . 06 : 79–102. doi :10.1142/S021819599600006X.
2. Aupperle, LJ; Conn, HE; ​​Keil, JM; O'Rourke, Joseph (1988). "Cubrir polígonos ortogonales con cuadrados". Actas de la 26.ª Conferencia Allerton. Commun. Control Comput. : 97–106.
3. Prof. Reuven Bar-Yehuda en comunicación personal
4. Culberson, JC; Reckhow, RA (1988). "Cubrir polígonos es difícil". [Actas 1988] 29.° Simposio anual sobre fundamentos de la informática . p. 601. doi :10.1109/sfcs.1988.21976. ISBN 978-0-8186-0877-3. Número de identificación del sujeto  34508387..
5. Chaiken, S.; Kleitman, DJ; Saks, M.; Shearer, J. (1981). "Recubrimiento de regiones mediante rectángulos". Revista SIAM sobre métodos algebraicos y discretos . 2 (4): 394. doi :10.1137/0602042.
6. Franzblau, DS; Kleitman, DJ (1984). "Un algoritmo para construir regiones con rectángulos". Actas del decimosexto simposio anual de la ACM sobre teoría de la computación - STOC '84 . p. 167. doi :10.1145/800057.808678. ISBN 978-0897911337.
7. Heinrich-Litan, L.; Lübbecke, ME (2007). "Revisión computacional de las cubiertas rectangulares". Journal of Experimental Algorithmics . 11 : 2.6. CiteSeerX 10.1.1.69.4576 . doi :10.1145/1187436.1216583. S2CID  619557. 
8. Kumar, VSA; Ramesh, H. (2003). "Recubrimiento de polígonos rectilíneos con rectángulos paralelos a los ejes". Revista SIAM de Computación . 32 (6): 1509. CiteSeerX 10.1.1.20.2664 . doi :10.1137/s0097539799358835. 
9. Keil, JM (1986). "Recubrimiento mínimo de un polígono ortogonal convexo horizontalmente". Actas del segundo simposio anual sobre geometría computacional - SCG '86 . págs. 43–51. doi :10.1145/10515.10520. ISBN 978-0897911948.
10. Culberson, J.; Reckhow, RA (1989). "Recubrimientos ortogonalmente convexos de polígonos ortogonales sin agujeros". Revista de Ciencias de la Computación y de Sistemas . 39 (2): 166. doi : 10.1016/0022-0000(89)90043-3 .
11. Motwani, R.; Raghunathan, A.; Saran, H. (1990). "Cubrir polígonos ortogonales con polígonos estrella: el enfoque del gráfico perfecto". Journal of Computer and System Sciences . 40 : 19–48. doi : 10.1016/0022-0000(90)90017-f .
12. Levcopoulos, C.; Gudmundsson, J. (1997). "Algoritmos de aproximación para cubrir polígonos con cuadrados y problemas similares". Técnicas de aleatorización y aproximación en informática . Apuntes de clase en informática. Vol. 1269. pág. 27. CiteSeerX 10.1.1.22.9094 . doi :10.1007/3-540-63248-4_3. ISBN.  978-3-540-63248-1., Grazyna Zwozniak, 1998
13. Stoyan, YG; Romanova, T.; Scheithauer, G.; Krivulya, A. (2009). "Cubrir una región poligonal con rectángulos". Optimización computacional y aplicaciones . 48 (3): 675. doi :10.1007/s10589-009-9258-1. S2CID  15599243.
14. Christ, T. (2011). "Más allá de la triangulación: cubrir polígonos con triángulos". Algoritmos y estructuras de datos . Apuntes de clase en informática. Vol. 6844. págs. 231–242. doi :10.1007/978-3-642-22300-6_20. ISBN 978-3-642-22299-3.
15. O'Rourke, J.; Supowit, K. (1983). "Algunos problemas de descomposición de polígonos NP-hard". IEEE Transactions on Information Theory . 29 (2): 181. doi :10.1109/tit.1983.1056648.
16. Abrahamsen, Mikkel. "Cubrir polígonos es aún más difícil" (PDF) . IEEE-FOCS .
17. Eidenbenz, S.; Widmayer, P. (2001). "Un algoritmo de aproximación para una cobertura convexa mínima con garantía de rendimiento logarítmico". Algoritmos — ESA 2001 . Apuntes de clase en informática. Vol. 2161. pág. 333. doi :10.1007/3-540-44676-1_28. ISBN 978-3-540-42493-2.
18. "Programa- FOCS 2023". FOCS 2023 . IEEE.
19. Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann (2017), El problema de la galería de arte está completo , arXiv : 1704.06969 , Bibcode :2017arXiv170406969A ${\displaystyle \exists \mathbb {R} }$
20. Fowler, Robert J.; Paterson, Michael S.; Tanimoto, Steven L. (13 de junio de 1981). "El empaquetamiento y el recubrimiento óptimos en el plano son NP-completos". Cartas de procesamiento de la información . 12 (3): 133–137. doi :10.1016/0020-0190(81)90111-3. ISSN  0020-0190.
21. Keil, JM (2000). "Descomposición de polígonos". Manual de geometría computacional . págs. 491–518. doi :10.1016/B978-044482537-7/50012-7. ISBN . 9780444825377.