Problema de la galería de arte

problema matematico

El problema de la galería de arte o problema del museo es un problema de visibilidad bien estudiado en geometría computacional . Se origina 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, el diseño de la galería de arte está representado por un polígono simple y cada guardia está representada por un punto en el polígono. Se dice que un conjunto de puntos protege un polígono si, para cada punto del polígono, hay uno 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 se puede aplicar en varios ámbitos, como en la robótica , cuando las inteligencias artificiales (IA) necesitan ejecutar movimientos en función de su entorno. Otros ámbitos donde se aplica este problema son en la edición de imágenes , los problemas de iluminación de un escenario o la instalación de infraestructuras para la alerta de catástrofes naturales.

Dos dimensiones

Cuatro guardias son capaces de cubrir esta galería.

Existen numerosas variaciones del problema original que también se conocen como problema de la galería de arte. En algunas versiones las protecciones se restringen 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 protecciones 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 , da un límite superior al número mínimo de guardias. Afirma:

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

Historia

La pregunta sobre cuántos vértices/vigilantes/guardias se necesitaban se la planteó a Chvátal 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 tres colores . ^[3] Chvátal tiene un enfoque más geométrico, mientras que Fisk utiliza resultados bien conocidos de la teoría de grafos .

La breve prueba de Fisk

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

La prueba de Steve Fisk es tan breve y elegante que fue elegida para incluirla en Pruebas de EL LIBRO . ^[4] La prueba es la siguiente:

En primer lugar, se triangula el polígono (sin añadir vértices extra), lo cual es posible porque la existencia de triangulaciones se prueba bajo ciertas condiciones verificadas. Los vértices del gráfico de triangulación resultante pueden tener 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 la menor cantidad de vértices define un conjunto de guardas válido con como máximo guardas. ${\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 que tiene menos vértices es azul o rojo, por lo que el polígono puede estar cubierto por  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 guardias en las esquinas se afloja a los guardias en cualquier punto que no sea 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 ángulo recto, solo se necesitan protectores. Hay al menos tres pruebas 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 decisión del problema de la galería de arte, se da como entrada un polígono y un número k , y se debe determinar si el polígono puede protegerse con k o menos guardias. Este problema es completo , al igual que la versión donde las protecciones están restringidas a los bordes del polígono. ^[10] Además, la mayoría de las otras variaciones estándar (como restringir las ubicaciones de las guardas a los vértices) son NP-hard . ^[11] ${\displaystyle \exists \mathbb {R} }$

Con respecto 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-duro, 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 polinómico. . Ghosh (1987) demostró que se puede lograr una aproximación logarítmica para el número mínimo de guardas de vértices 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 cuyo ratio de aproximación es el logaritmo del número óptimo de guardias en lugar del número de vértices de polígonos. ^[12] Para los guardias sin restricciones, el número infinito de posibles posiciones de guardia hace que el problema sea aún más difícil. Sin embargo, al restringir los guardias para que se encuentren en una cuadrícula fina, se puede derivar un algoritmo de aproximación logarítmica más complicado bajo algunos supuestos adicionales leves, como lo muestran Bonnet y Miltzow (2017). Sin embargo, se conocen algoritmos eficientes para encontrar un conjunto de, como máximo, guardias de vértices, que coincidan con el límite superior de Chvátal. David Avis y Godfried Toussaint  (1981) demostraron que la ubicación de estos guardias se puede calcular en un tiempo O (n log n) en el peor de los casos, mediante 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 las protecciones de vértices y bordes. 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 un borde. Krohn y Nilsson (2013) presentaron un algoritmo de aproximación que calcula en tiempo polinómico un conjunto de guardas de vértices para un polígono monótono tal que el tamaño del conjunto de guardas es como máximo 30 veces el número óptimo de guardas de vértices. Bhattacharya, Ghosh y Roy (2017) presentaron un algoritmo de aproximación que calcula en tiempo O(n ² ) un conjunto de protección de vértices para un polígono simple que es débilmente visible desde un borde, de modo que el tamaño del conjunto de protección 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 utilizando protectores de vértices y protectores de bordes. Para el vértice que protege la subclase de polígonos simples que son débilmente visibles desde un borde, Ashur et al. (2019).

Couto, de Rezende y de Souza (2011) propusieron un algoritmo exacto para las protecciones de vértices. Los autores llevaron a cabo extensos experimentos computacionales con varias clases de polígonos, demostrando 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 estos casos están disponibles para descargar. ^[13]

Tres dimensiones

Un poliedro ortogonal con cada vértice invisible 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 por 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 protector en cada vértice no garantizará que todo el museo esté bajo observación. Aunque se inspeccionaría toda la superficie del poliedro, en algunos poliedros hay puntos en el interior que podrían no estar bajo vigilancia. ^[15]

Ver también

• Cubrir un polígono rectilíneo con polígonos en estrella
• Polígono en forma de estrella , clase de polígono para el cual el problema de la galería de arte se puede resolver con una sola guarda.
• Problema de iluminación : ¿basta con una sola guarda si las paredes tienen espejos?

Notas

1. Para demostrar la colorabilidad de las triangulaciones de polígonos, observamos que el gráfico dual débil de la triangulación (el gráfico 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 gráfico dual sería forman 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 es 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 coloración triple 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); Saco 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 , Ph.D. tesis, Universidad Johns Hopkins.
• Aigner, Martín ; Ziegler, Günter M. (2018), "Capítulo 40: Cómo proteger un museo", Pruebas del LIBRO (6.a ed.), Berlín: Springer, págs. 281–283, doi :10.1007/978-3-662- 57265-8, ISBN 978-3-662-57264-1, señor  3823190.
• Asur, Stav; Filtser, Omrit; Katz, Mateo J.; Saban, Rachel (2019), "Gráficos similares al terreno: PTAS para proteger terrenos y polígonos débilmente visibles", en Bampis, Evripidis; Megow, Nicole (eds.), Aproximación y algoritmos en línea: 17.° taller internacional, WAOA 2019, Múnich, Alemania, 12 y 13 de septiembre de 2019, artículos seleccionados revisados , Lecture Notes in Computer Science, vol. 11926, Berlín: Springer, págs. 1 a 17, doi :10.1007/978-3-030-39479-0_1, ISBN 978-3-030-39478-3, S2CID  210936577.
• Avis, D .; Toussaint, GT (1981), "Un algoritmo eficaz para descomponer un polígono en polígonos en 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 utilizando Vertex Guards , arXiv : 1712.05492
• Bhattacharya, Pritam; Ghosh, Subir Kumar; Roy, Bodhayan (2017), "Aproximabilidad de proteger polígonos de visibilidad débil", Matemáticas aplicadas discretas , 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), "Cubiertas de conjuntos casi óptimos en dimensiones finitas de VC", 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", Transacciones internacionales en investigación operativa , 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 de tiempo pseudopolinomial O (logn) para problemas de galerías de arte", Proc. Trabajo. Algoritmos y estructuras de datos , Apuntes de conferencias sobre informática, 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, S2CID  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 original (PDF) el 2003-06-24.
• Fisk, S. (1978), "Una breve prueba 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 Información , págs. 429–434.
• Kahn, J.; Klawe, M .; Kleitman, D. (1983), "Las galerías tradicionales requieren menos vigilantes", SIAM J. Algebr. Métodos discretos , 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, S2CID  15752916.
• O'Rourke, Joseph (1987), Teoremas y algoritmos de la galería de arte , Oxford University Press, ISBN 0-19-503965-3.
• O'Rourke, José ; Supowit, Kenneth J. (1983), "Algunos problemas de descomposición de polígonos duros NP", IEEE Transactions on Information Theory , 29 (2): 181–190, doi :10.1109/TIT.1983.1056648, MR  0712374.
• Saco, JR ; Toussaint, GT (1988), "Colocación de guardias en polígonos rectilíneos", en Toussaint, GT (ed.), Morfología computacional , Holanda Septentrional, págs..
• 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.), Manual de geometría computacional , Holanda Septentrional, págs. 973–1027, doi :10.1016/B978-044482537-7/50023-1, ISBN 978-0-444-82537-7.
• Valtr, P. (1998), "Protegiendo galerías donde ningún punto ve un área pequeña", Israel Journal of Mathematics , 104 (1): 1–16, doi : 10.1007/BF02897056.