Problema de la galería de arte

Problema matemático

El problema de la galería de arte o problema del museo es un problema de visibilidad muy estudiado en geometría computacional . Tiene su origen en el siguiente problema del mundo real:

"En una galería de arte , ¿cuál es el número mínimo de guardias que juntos pueden observar toda la galería?"

En la versión geométrica del problema, la disposición de la galería de arte se representa mediante un polígono simple y cada guardia está representado por un punto del polígono. Se dice que un conjunto de puntos protege un polígono si, para cada punto del polígono, hay alguno tal que el segmento de línea entre y no sale del polígono. ${\displaystyle S}$ ${\displaystyle p}$ ${\displaystyle q\in S}$ ${\displaystyle p}$ ${\displaystyle q}$

El problema de la galería de arte puede aplicarse en varios dominios como por ejemplo en la robótica , cuando las inteligencias artificiales (IA) necesitan ejecutar movimientos en función de su entorno. Otros dominios, donde se aplica este problema, son en la edición de imágenes , problemas de iluminación de un escenario o instalación de infraestructuras para la alerta de desastres naturales.

Dos dimensiones

Cuatro guardias pueden cubrir esta galería.

Existen numerosas variantes del problema original, también conocido como el problema de la galería de arte. En algunas versiones, las protecciones se limitan al perímetro o incluso a los vértices del polígono. Algunas versiones requieren que solo se proteja el perímetro o un subconjunto del perímetro.

Resolver la versión en la que se deben colocar protectores en los vértices y solo es necesario proteger los vértices es equivalente a resolver el problema del conjunto dominante en el gráfico de visibilidad del polígono.

Teorema de la galería de arte de Chvátal

El teorema de la galería de arte de Chvátal, que lleva el nombre de Václav Chvátal , establece un límite superior para el número mínimo de guardias. Dice:

"Para proteger un polígono simple con vértices, las protecciones son siempre suficientes y a veces necesarias." ${\displaystyle n}$ ${\displaystyle \left\lfloor n/3\right\rfloor }$

Historia

La pregunta sobre cuántos vértices/vigilantes/guardias eran necesarios, fue planteada a Chvátal por Victor Klee en 1973. ^[1] Chvátal lo demostró poco después. ^[2] La prueba de Chvátal fue posteriormente simplificada por Steve Fisk, mediante un argumento de 3 coloraciones . ^[3] Chvátal tiene un enfoque más geométrico, mientras que Fisk utiliza resultados bien conocidos de la teoría de grafos .

Prueba corta de Fisk

Una coloración tridimensional de los vértices de un polígono triangulado. Los vértices azules forman un conjunto de tres guardas, tan pocas como garantiza el teorema de la galería de arte. Sin embargo, este conjunto no es óptimo: el mismo polígono puede estar protegido por solo dos guardas.

La prueba de Steve Fisk es tan breve y elegante que fue elegida para su inclusión en Pruebas del LIBRO . ^[4] La prueba es la siguiente:

En primer lugar, el polígono se triangula (sin añadir vértices adicionales), lo que es posible, porque la existencia de triangulaciones se prueba bajo ciertas condiciones verificadas. Los vértices del gráfico de triangulación resultante pueden ser de 3 colores . ^[a] Claramente, bajo una coloración de 3 colores, cada triángulo debe tener los tres colores. Los vértices con cualquier color forman un conjunto de protección válido, porque cada triángulo del polígono está protegido por su vértice con ese color. Dado que los tres colores dividen los n vértices del polígono, el color con menos vértices define un conjunto de protección válido con, como máximo, protectores. ${\displaystyle \lfloor n/3\rfloor }$

Ilustración de la prueba

Para ilustrar la prueba, consideremos el siguiente polígono. El primer paso es triangular el polígono (ver Figura 1 ). Luego, se aplica una coloración adecuada ( Figura 2 ) y se observa que hay vértices  rojos,  azules y  verdes. El color con menos vértices es azul o rojo, por lo que el polígono puede cubrirse con  guardas ( Figura 3 ). Esto concuerda con el teorema de la galería de arte, porque el polígono tiene  vértices y . ${\displaystyle 3}$ ${\displaystyle 4}$ ${\displaystyle 4}$ ${\displaystyle 6}$ ${\displaystyle 4}$ ${\displaystyle 14}$ ${\displaystyle \left\lfloor {\frac {14}{3}}\right\rfloor =4}$

• 
  Figura 1
• 
  Figura 2
• 
  Figura 3

Generalizaciones

El límite superior de Chvátal sigue siendo válido si la restricción a los protectores en las esquinas se relaja a los protectores en cualquier punto no exterior al polígono.

Hay varias otras generalizaciones y especializaciones del teorema original de la galería de arte. ^[6] Por ejemplo, para polígonos ortogonales , aquellos cuyos bordes/paredes se encuentran en ángulos rectos, solo se necesitan guardas. Hay al menos tres demostraciones distintas de este resultado, ninguna de ellas simple: por Kahn, Klawe y Kleitman ; por Lubiw ; y por Sack y Toussaint . ^{[7] [8]} ${\displaystyle \lfloor n/4\rfloor }$

Un problema relacionado pregunta por el número de guardias para cubrir el exterior de un polígono arbitrario (el "Problema de la Fortaleza"): a veces son necesarios y siempre suficientes si los guardias se colocan en el límite del polígono, mientras que a veces son necesarios y siempre suficientes si los guardias se colocan en cualquier lugar del exterior del polígono. ^[9] En otras palabras, el exterior infinito es más difícil de cubrir que el interior finito. ${\displaystyle \lceil n/2\rceil }$ ${\displaystyle \lceil n/3\rceil }$

Complejidad computacional

En las versiones del problema de la galería de arte que utilizan problemas de decisión , se da como entrada un polígono y un número k y se debe determinar si el polígono se puede proteger con k o menos protecciones. Este problema es -completo , al igual que la versión en la que las protecciones están restringidas a los bordes del polígono. ^[10] Además, la mayoría de las otras variaciones estándar (como la restricción de las ubicaciones de las protecciones a los vértices) son NP-hard . ^[11] ${\displaystyle \exists \mathbb {R} }$

En cuanto a los algoritmos de aproximación para el número mínimo de guardias, Eidenbenz, Stamm y Widmayer (2001) demostraron que el problema es APX-hard, lo que implica que es poco probable que se pueda lograr una relación de aproximación mejor que alguna constante fija mediante un algoritmo de aproximación de tiempo polinomial . Ghosh (1987) demostró que se puede lograr una aproximación logarítmica para el número mínimo de guardias de vértice discretizando el polígono de entrada en subregiones convexas y luego reduciendo el problema a un problema de cobertura de conjuntos . Como mostró Valtr (1998), el sistema de conjuntos derivado de un problema de galería de arte tiene una dimensión VC acotada , lo que permite la aplicación de algoritmos de cobertura de conjuntos basados ​​en ε-nets cuya relación de aproximación es el logaritmo del número óptimo de guardias en lugar del número de vértices del polígono. ^[12] Para guardias sin restricciones, el número infinito de posiciones de guardia potenciales hace que el problema sea aún más difícil. Sin embargo, al restringir los protectores para que se encuentren en una cuadrícula fina, se puede derivar un algoritmo de aproximación logarítmica más complicado bajo algunas suposiciones adicionales leves, como lo muestran Bonnet y Miltzow (2017). Sin embargo, se conocen algoritmos eficientes para encontrar un conjunto de, como máximo, protectores de vértices, que coincidan con el límite superior de Chvátal. David Avis y Godfried Toussaint  (1981) demostraron que una ubicación para estos protectores se puede calcular en tiempo O(n log n) en el peor de los casos, a través de un algoritmo de divide y vencerás . Kooshesh y Moret (1992) dieron un algoritmo de tiempo lineal utilizando la prueba corta de Fisk y el algoritmo de triangulación del plano de tiempo lineal de Bernard Chazelle . ${\displaystyle \left\lfloor n/3\right\rfloor }$

Para polígonos simples que no contienen agujeros, Ghosh conjeturó la existencia de un algoritmo de aproximación de factor constante para protectores de vértices y aristas. Inicialmente, se demostró que la conjetura de Ghosh era cierta para los protectores de vértices en dos subclases especiales de polígonos simples, a saber, polígonos monótonos y polígonos débilmente visibles desde una arista. Krohn y Nilsson (2013) presentaron un algoritmo de aproximación que calcula en tiempo polinomial un conjunto de protectores de vértices para un polígono monótono tal que el tamaño del conjunto de protectores es como máximo 30 veces el número óptimo de protectores de vértices. Bhattacharya, Ghosh y Roy (2017) presentaron un algoritmo de aproximación que calcula en tiempo O(n ² ) un conjunto de protectores de vértices para un polígono simple que es débilmente visible desde una arista tal que el tamaño del conjunto de protectores es como máximo 6 veces el número óptimo de protectores de vértices. Posteriormente, Bhattacharya, Ghosh y Pal (2017) afirmaron haber resuelto la conjetura por completo al presentar algoritmos de aproximación de factor constante para proteger polígonos simples generales mediante protectores de vértices y protectores de aristas. Para proteger los vértices de la subclase de polígonos simples que son débilmente visibles desde una arista, Ashur et al. (2019) propusieron un esquema de aproximación de tiempo polinomial .

Couto, de Rezende y de Souza (2011) propusieron un algoritmo exacto para los protectores de vértices. Los autores realizaron experimentos computacionales extensos con varias clases de polígonos y demostraron que se pueden encontrar soluciones óptimas en tiempos de cálculo relativamente pequeños, incluso para instancias asociadas a miles de vértices. Los datos de entrada y las soluciones óptimas para estas instancias están disponibles para su descarga. ^[13]

Tres dimensiones

Un poliedro ortogonal con todos los vértices invisibles desde su centro ^[14]

Un ejemplo de un poliedro con puntos interiores no visibles desde ningún vértice, la figura de la derecha muestra una sección transversal a través de su centro, O, y paralela a ABCD.

Panorama esférico de 360° desde el interior del poliedro de arriba que muestra que todos los vértices están ocultos por las caras amarillas
( ver como un panorama interactivo de 360° )

Si un museo se representa en tres dimensiones como un poliedro , entonces poner un guardia en cada vértice no garantizará que todo el museo esté bajo vigilancia. Aunque se inspeccionaría toda la superficie del poliedro, en el caso de algunos poliedros hay puntos en el interior que podrían no estar bajo vigilancia. ^[15]

Véase también

• Cubriendo un polígono rectilíneo con polígonos estrellados
• Polígono en forma de estrella , una clase de polígono para el cual el problema de la galería de arte se puede resolver con una sola protección.
• Problema de iluminación : ¿es suficiente un solo protector si las paredes son espejadas?

Notas

1. Para probar la 3-colorabilidad de las triangulaciones de polígonos, observamos que el grafo dual débil de la triangulación (el grafo no dirigido que tiene un vértice por triángulo y una arista por par de triángulos adyacentes) es un árbol , ya que cualquier ciclo en el grafo dual formaría el límite de un agujero en el polígono, contrariamente a la suposición de que no tiene agujeros. Siempre que haya más de un triángulo, el grafo dual (como cualquier árbol) debe tener un vértice con un solo vecino, correspondiente a un triángulo que sea adyacente a otros triángulos a lo largo de solo uno de sus lados. El polígono más pequeño formado al eliminar este triángulo tiene una 3-coloración por inducción matemática , y esta coloración se extiende fácilmente al vértice adicional del triángulo eliminado. ^[5]

Referencias

1. O'Rourke (1987), pág. 1.
2. Chvátal (1975).
3. Fisk (1978).
4. Aigner y Ziegler (2018).
5. O'Rourke (1987), pág. 13.
6. Shermer (1992); Urrutia (2000)
7. Kahn, Klawe y Kleitman (1983); Lubiw (1985); Sack y Toussaint (1988).
8. O'Rourke (1987), págs. 31–80.
9. O'Rourke (1987), págs. 146-154.
10. Abrahamsen, Adamaszek y Miltzow (2022).
11. O'Rourke y Supowit (1983); Lee y Lin (1986).
12. Brönnimann y Goodrich (1995).
13. Couto, de Rezende y de Souza (2011).
14. Eryk Lipka, Una nota sobre galerías de arte minimalistas , 2019
15. O'Rourke (1987), pág. 255.

Fuentes

• Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann (2022), "El problema de la galería de arte está completo", Journal of the ACM , 69 (1): A4:1–A4:70, arXiv : 1704.06969 , doi :10.1145/3486220, MR  4402363, S2CID  245059672 ${\displaystyle \exists {\mathbb {R}}}$
• Aggarwal, A. (1984), El teorema de la galería de arte: sus variaciones, aplicaciones y aspectos algorítmicos , tesis doctoral, Universidad Johns Hopkins.
• Aigner, Martin ; Ziegler, Günter M. (2018), "Capítulo 40: Cómo proteger un museo", Pruebas de EL LIBRO (6.ª ed.), Berlín: Springer, pp. 281–283, doi :10.1007/978-3-662-57265-8, ISBN 978-3-662-57264-1, Sr.  3823190.
• Ashur, Stav; Filtser, Omrit; Katz, Matthew J.; Saban, Rachel (2019), "Gráficos similares al terreno: PTAS para proteger polígonos y terrenos débilmente visibles", en Bampis, Evripidis; Megow, Nicole (eds.), Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Múnich, Alemania, 12 y 13 de septiembre de 2019, Documentos revisados ​​seleccionados , Lecture Notes in Computer Science, vol. 11926, Berlín: Springer, págs. 1–17, doi :10.1007/978-3-030-39479-0_1, ISBN 978-3-030-39478-3, Número de identificación del sujeto  210936577.
• Avis, D. ; Toussaint, GT (1981), "Un algoritmo eficiente para descomponer un polígono en polígonos con forma de estrella" (PDF) , Reconocimiento de patrones , 13 (6): 395–398, Bibcode :1981PatRe..13..395A, doi :10.1016/0031-3203(81)90002-9.
• Bhattacharya, Pritam; Ghosh, Subir Kumar; Pal, Sudebkumar (2017), Algoritmos de aproximación constante para proteger polígonos simples mediante protectores de vértices , arXiv : 1712.05492
• Bhattacharya, Pritam; Ghosh, Subir Kumar; Roy, Bodhayan (2017), "Aproximabilidad de la protección de polígonos de visibilidad débil", Discrete Applied Mathematics , 228 : 109–129, arXiv : 1409.4621 , doi : 10.1016/j.dam.2016.12.015, MR  3662965, S2CID  9916523
• Bonnet, Édouard; Miltzow, Tillmann (2017), "Un algoritmo de aproximación para el problema de la galería de arte", en Aronov, Boris; Katz, Matthew J. (eds.), 33.er Simposio internacional sobre geometría computacional, SoCG 2017, 4 al 7 de julio de 2017, Brisbane, Australia , LIPIcs, vol. 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, págs. 20:1–20:15, arXiv : 1607.05527 , doi : 10.4230/LIPIcs.SoCG.2017.20 , MR  3685692, S2CID  1293138.
• Brönnimann, H.; Goodrich, MT (1995), "Coberturas de conjuntos casi óptimas en dimensión VC finita", Geometría discreta y computacional , 14 (1): 463–479, doi : 10.1007/BF02570718.
• Chvátal, V. (1975), "Un teorema combinatorio en geometría plana", Journal of Combinatorial Theory, Serie B , 18 : 39–41, doi : 10.1016/0095-8956(75)90061-1.
• Couto, M.; de Rezende, P.; de Souza, C. (2011), "Un algoritmo exacto para minimizar las protecciones de vértices en galerías de arte", International Transactions in Operational Research , 18 (4): 425–448, doi :10.1111/j.1475-3995.2011.00804.x.
• de Rezende, P.; de Souza, C.; Couto, M.; Tozoni, D. (2011), "El problema de la galería de arte con Vertex Guards", Proyecto Problema de la galería de arte , Instituto de Computação.
• Deshpande, Ajay; Kim, Taejung; Demaine, Erik D .; Sarma, Sanjay E. (2007), "Un algoritmo de aproximación temporal pseudopolinomial O(logn) para problemas de galerías de arte", Proc. Worksh. Algorithms and Data Structures , Lecture Notes in Computer Science, vol. 4619, Springer-Verlag, págs. 163–174, doi :10.1007/978-3-540-73951-7_15, hdl : 1721.1/36243 , ISBN 978-3-540-73948-7, Número de identificación del sujeto  9148459.
• Eidenbenz, S.; Stamm, C.; Widmayer, P. (2001), "Resultados de inaproximabilidad para proteger polígonos y terrenos" (PDF) , Algorithmica , 31 (1): 79–113, doi :10.1007/s00453-001-0040-8, S2CID  14532511, archivado desde el original (PDF) el 24 de junio de 2003.
• Fisk, S. (1978), "Una breve demostración del teorema del vigilante de Chvátal", Journal of Combinatorial Theory, Serie B , 24 (3): 374, doi : 10.1016/0095-8956(78)90059-X.
• Ghosh, SK (1987), "Algoritmos de aproximación para problemas de galerías de arte", Proc. Congreso de la Sociedad Canadiense de Procesamiento de la Información , págs. 429–434.
• Kahn, J.; Klawe, M .; Kleitman, D. (1983), "Las galerías tradicionales requieren menos vigilantes", SIAM J. Algebr. Discrete Methods , 4 (2): 194–206, doi :10.1137/0604020.
• Kooshesh, AA; Moret, BME (1992), "Tres colores de los vértices de un polígono simple triangulado", Reconocimiento de patrones , 25 (4): 443, Bibcode :1992PatRe..25..443K, doi :10.1016/0031-3203(92)90093-X.
• Krohn, Erik A.; Nilsson, Bengt J. (2013), "Protección aproximada de polígonos monótonos y rectilíneos", Algorithmica , 66 (3): 564–594, doi :10.1007/s00453-012-9653-3, hdl : 2043/11487 , MR  3044626, S2CID  1458082.
• Lee, DT ; Lin, AK (1986), "Complejidad computacional de los problemas de las galerías de arte", IEEE Transactions on Information Theory , 32 (2): 276–282, doi :10.1109/TIT.1986.1057165.
• Lubiw, A. (1985), "Descomposición de regiones poligonales en cuadriláteros convexos", Proc. 1er Simposio ACM sobre Geometría Computacional , págs. 97-106, doi :10.1145/323233.323247, ISBN 0-89791-163-6, Número de identificación del sujeto  15752916.
• O'Rourke, Joseph (1987), Teoremas y algoritmos de la galería de arte , Oxford University Press, ISBN 0-19-503965-3.
• O'Rourke, Joseph ; Supowit, Kenneth J. (1983), "Algunos problemas de descomposición de polígonos NP-hard", IEEE Transactions on Information Theory , 29 (2): 181–190, doi :10.1109/TIT.1983.1056648, MR  0712374.
• Sack, JR ; Toussaint, GT (1988), "Ubicación de la protección en polígonos rectilíneos", en Toussaint, GT (ed.), Computational Morphology , North-Holland, págs. 153–176.
• Shermer, Thomas (1992), "Resultados recientes en galerías de arte" (PDF) , Actas del IEEE , 80 (9): 1384–1399, doi :10.1109/5.163407.
• Urrutia, Jorge (2000), "Galería de arte y problemas de iluminación", en Sack, J. -R.; Urrutia, Jorge (eds.), Handbook of Computational Geometry , North-Holland, pp. 973–1027, doi :10.1016/B978-044482537-7/50023-1, ISBN 978-0-444-82537-7.
• Valtr, P. (1998), "Guardando galerías donde ningún punto ve un área pequeña", Israel Journal of Mathematics , 104 (1): 1–16, doi : 10.1007/BF02897056.