El problema de la galería de arte o del museo es un problema de visibilidad bien estudiado en geometría computacional . Se origina en un problema del mundo real de proteger una galería de arte con 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. Un conjunto de puntos se dice que protege un polígono si, para cada punto en el polígono, hay algunos tal que el segmento de línea entre y no sale del polígono.
Dos dimensiones
Existen numerosas variaciones del problema original que también se conocen como el problema de la galería de arte. En algunas versiones, los guardias están restringidos 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 las protecciones deben colocarse en los vértices y solo los vértices deben protegerse 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. Se afirma que Los guardias son siempre suficientes y, a veces, necesarios para proteger un polígono simple con vértices.
La pregunta sobre cuántos vértices / vigilantes / guardias se necesitaban fue planteada a Chvátal por Victor Klee en 1973. [1] Chvátal lo demostró poco después. [2] La demostración de Chvátal fue posteriormente simplificada por Steve Fisk, mediante un argumento de tres colores . [3]
Prueba corta de Fisk
La prueba de Steve Fisk es tan corta y elegante que fue elegida para incluirla en Pruebas del LIBRO . [4] La prueba es la siguiente:
Primero, el polígono se triangula (sin agregar vértices adicionales). Los vértices del gráfico de triangulación resultante pueden tener tres colores . [a] Claramente, bajo tres 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 protección válido con como máximo guardias.
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 una serie de otras generalizaciones y especializaciones del teorema de la galería de arte original. [6] Por ejemplo, para polígonos ortogonales , aquellos cuyos bordes / paredes se encuentran en ángulos rectos, solose necesitan guardias. 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]
Un problema relacionado pide el número de guardias para cubrir el exterior de un polígono arbitrario (el "Problema de la Fortaleza"): a veces son necesarias y siempre suficientes. En otras palabras, el exterior infinito es más difícil de cubrir que el interior finito. [9]
Complejidad computacional
En las versiones de problemas de decisión del problema de la galería de arte, se da como entrada tanto un polígono como un número k , y debe determinar si el polígono se puede proteger con k guardias o menos. Este problema es-completa , como es la versión donde los guardias están restringidos a los bordes del polígono. [10] Además, la mayoría de las otras variaciones estándar (como restringir las ubicaciones de guarda a los vértices) son NP-hard . [11]
Con respecto a los algoritmos de aproximación para el número mínimo de guardias, Eidenbenz, Stamm & Widmayer (2001) demostraron que el problema es APX-hard, lo que implica que es poco probable que una relación de aproximación mejor que alguna constante fija pueda lograrse mediante un algoritmo de aproximación de tiempo polinomial. . Sin embargo, hasta hace muy poco no se conocía un algoritmo que lograra una relación de aproximación constante. Ghosh (1987) mostró que se puede lograr una aproximación logarítmica para el número mínimo de guardias de vértices discretizando el polígono de entrada en subregiones convexas y luego reduciendo el problema a un problema de cobertura de conjunto . Como mostró Valtr (1998) , el sistema de conjuntos derivado de un problema de galería de arte tiene una dimensión de VC acotada , lo que permite la aplicación de algoritmos de cobertura de conjuntos basados en redes ε cuya relación de aproximación es el logaritmo del número óptimo de guardias en lugar del número de vértices de polígono. [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 algunas suposiciones adicionales leves, como lo muestran Bonnet y Miltzow (2017) . Sin embargo, los algoritmos eficientes son conocidos por encontrar un conjunto de como máximoguardias de vértice, que coinciden con el límite superior de Chvátal. David Avis y Godfried Toussaint ( 1981 ) demostraron que la ubicación de estos guardias puede calcularse en 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 .
Para polígonos simples que no contienen huecos, Ghosh conjeturó la existencia de un algoritmo de aproximación de factor constante para protectores 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 polinomial un conjunto de guardias de vértice para un polígono monótono de modo que el tamaño del conjunto de guardias sea como máximo 30 veces el número óptimo de guardias de vértices. Bhattacharya, Ghosh & Roy (2017) presentaron un algoritmo de aproximación que calcula en el tiempo O (n 2 ) un conjunto de guardias de vértice para un polígono simple que es débilmente visible desde un borde, de manera que el tamaño del conjunto de guardias es como máximo 6 veces el número óptimo de guardias de vértice. Posteriormente, Bhattacharya, Ghosh & Pal (2017) afirmaron haber resuelto la conjetura por completo al presentar algoritmos de aproximación de factores constantes para proteger polígonos simples generales utilizando protectores de vértices y protectores de bordes. Para vértice que guarda la subclase de polígonos simples que son débilmente visible desde un borde, un esquema de aproximación de tiempo polinómico fue propuesto por Ashur et al. (2019) .
Couto, de Rezende & de Souza (2011) propusieron un algoritmo exacto para los protectores de vértices. Los autores llevaron a cabo extensos experimentos computacionales con varias clases de polígonos que muestran 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 descargar. [13]
Tres dimensiones
Si un museo está representado en tres dimensiones como un poliedro , poner una guardia en cada vértice no asegurará que todo el museo esté bajo observación. Si bien se inspeccionaría toda la superficie del poliedro, para algunos poliedros hay puntos en el interior que podrían no estar bajo vigilancia. [14]
Posibles escenarios de uso del problema de la galería de arte
El problema de la galería de arte se puede utilizar para colocar varias cámaras cuando el objetivo es cubrir un área grande en el campo de visión de las cámaras, utilizando un número mínimo de cámaras.
Ver también
- Cubriendo un polígono rectilíneo con polígonos en estrella
- Polígono en forma de estrella , una clase de polígono para el que el problema de la galería de arte se puede resolver con una sola guardia.
Notas
- ^ Para probar la triple coloración de las triangulaciones poligonales, observamos que el gráfico dual débilde la triangulación (el gráfico no dirigido que tiene un vértice por triángulo y un borde 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 gráfico dual (como cualquier árbol) debe tener un vértice con un solo vecino, correspondiente a un triángulo 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 un color 3 por inducción matemática , y este color se extiende fácilmente al vértice adicional del triángulo eliminado. [5]
Referencias
- ^ O'Rourke (1987) , p. 1.
- ^ Chvátal (1975) .
- ^ Fisk (1978) .
- ^ Aigner y Ziegler (2018) .
- ^ O'Rourke (1987) , p. 13.
- ^ Shermer (1992) .
- ^ Kahn, Klawe y Kleitman (1983) ; Lubiw (1985) ; Sack y Toussaint (1988) .
- ^ O'Rourke (1987) , págs. 31–80.
- ^ O'Rourke (1987) , págs. 146-154.
- ^ Abrahamsen, Adamaszek y Miltzow (2018) .
- ^ O'Rourke y Supowit (1983) ; Lee y Lin (1986) .
- ^ Brönnimann y Goodrich (1995) .
- ^ Couto, de Rezende y de Souza (2011) .
- ^ O'Rourke (1987) , p. 255.
Fuentes
- Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann (2018), "El problema de la galería de arte es-complete ", en Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (eds.), Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Ángeles, CA, EE. UU., 25 al 29 de junio de 2018 , ACM, págs. 65–73, arXiv : 1704.06969 , doi : 10.1145 / 3188745.3188868 , MR 3826234
- 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, Martin ; Ziegler, Günter M. (2018), "Capítulo 40: Cómo proteger un museo", Pruebas de THE BOOK (6a ed.), Berlín: Springer, págs. 281-283, doi : 10.1007 / 978-3-662- 57265-8 , ISBN 978-3-662-57264-1, MR 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, Munich, Alemania, 12 al 13 de septiembre de 2019, Revised Selected Papers , Lecture Notes in Computer Science, 11926 , Berlín: Springer, págs.1 –17, doi : 10.1007 / 978-3-030-39479-0_1.
- Avis, D .; Toussaint, GT (1981), "Un algoritmo eficiente para descomponer un polígono en polígonos en forma de estrella" (PDF) , Reconocimiento de patrones , 13 (6): 395–398, 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 usando Vertex Guards , arXiv : 1712.05492
- Bhattacharya, Pritam; Ghosh, Subir Kumar; Roy, Bodhayan (2017), "Aproximación 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
- 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 ° Simposio Internacional sobre Geometría Computacional, SoCG 2017, 4-7 de julio de 2017, Brisbane, Australia , LIPIcs, 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.
- Brönnimann, H .; Goodrich, MT (1995), "Cubiertas 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 las 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 los guardias de vértice" , Proyecto Problema de la galería de arte , Instituto de Computação.
- Deshpande, Ajay; Kim, Taejung; Demaine, Erik D .; Sarma, Sanjay E. (2007), "A Pseudopolynomial Time O (logn) -Approximation Algorithm for Art Gallery Problems", Proc. Worksh. Algoritmos y estructuras de datos , Lecture Notes in Computer Science, 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.
- 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 , archivado desde el 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ía 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. 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, 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.
- Lee, DT ; Lin, AK (1986), "La 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.
- 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 duros NP", IEEE Transactions on Information Theory , 29 (2): 181-190, doi : 10.1109 / TIT.1983.1056648 , MR 0712374.
- Sack, JR ; Toussaint, GT (1988), "Colocación de guardias en polígonos rectilíneos", en Toussaint, GT (ed.), Computational Morphology , North-Holland, págs. 153-176.
- Shermer, Thomas (1992), "Recent Results in Art Galleries" (PDF) , Proceedings of the IEEE , 80 (9): 1384-1399, doi : 10.1109 / 5.163407.
- Valtr, P. (1998), "Vigilando galerías donde ningún punto ve un área pequeña", Israel J. Math. , 104 (1): 1–16, doi : 10.1007 / BF02897056.