Hispanopedia Wiki
Articulo de referencia

Problema de la galería de arte

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

Hispanopedia WikiContenido en espanolLectura gratuita

El problema de la galería de arte o del museo es un problema de visibilidad ampliamente 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, en conjunto, pueden vigilar toda la galería?"

En la versión geométrica del problema, la disposición de la galería de arte está representada por un polígono simple y cada guardia está representado por un punto en el polígono. Un conjuntoS{\displaystyle S}Se dice que un conjunto de puntos protege un polígono si, para cada puntopag{\displaystyle p}En el polígono hay algoq∈S{\displaystyle q\in S}de tal manera que el segmento de línea entrepag{\displaystyle p}yq{\displaystyle q}no abandona el polígono.

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

Dos dimensiones

Cuatro guardias pueden vigilar esta galería.

Existen numerosas variantes del problema original, también conocidas 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. Otras versiones requieren que solo se vigile el perímetro o una parte de él.

Resolver la versión en la que los guardianes deben colocarse en los vértices y solo los vértices necesitan ser protegidos es equivalente a resolver el problema del conjunto dominante en el grafo de visibilidad del polígono.

El teorema de la galería de arte de Chvátal, que lleva el nombre de Václav Chvátal , proporciona una cota superior para el número mínimo de guardias. En él se afirma:

"Para proteger un polígono simple connorte{\displaystyle n}vértices,⌊norte/3⌋{\displaystyle \left\lfloor n/3\right\rfloor }Los guardias siempre son suficientes y, a veces, necesarios.

Historia

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 3-coloración . [ 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 de tres colores para los vértices de un polígono triangulado. Los vértices azules forman un conjunto de tres guardianes, el mínimo garantizado por 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 guardianes (por ejemplo, los dos guardianes azules de la izquierda).

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

Primero, el polígono se triangula (sin añadir vértices adicionales), lo cual es posible, ya que la existencia de triangulaciones se demuestra bajo ciertas condiciones verificadas. Los vértices del grafo de triangulación resultante pueden ser tricoloreados . [ a ] Claramente, bajo una tricoloración, cada triángulo debe tener los tres colores. Los vértices con cualquier color forman un conjunto de guarda 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 el menor número de vértices define un conjunto de guarda válido con como máximo n vértices.⌊norte/3⌋{\displaystyle \lfloor n/3\rfloor }guardias.

Generalizaciones

El límite superior de Chvátal sigue siendo válido si la restricción a los guardianes en las esquinas se flexibiliza para incluir guardianes en cualquier punto que no esté fuera del polígono.

Existen varias otras generalizaciones y especializaciones del teorema original de la galería de arte. [ 7 ] Por ejemplo, para polígonos ortogonales , aquellos cuyos bordes/paredes se encuentran en ángulo recto, solo⌊norte/4⌋{\displaystyle \lfloor n/4\rfloor }Se necesitan guardias. Hay al menos tres pruebas distintas de este resultado, ninguna de ellas sencilla: por Kahn, Klawe y Kleitman ; por Lubiw ; y por Sack y Toussaint . [ 8 ] [ 9 ]

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

Complejidad computacional

En las versiones de problemas de decisión del problema de la galería de arte, se proporciona como entrada un polígono y un número k , y se debe determinar si el polígono puede ser custodiado con k o menos guardias. Este problema es∃R{\displaystyle \exists \mathbb {R} }-completa , como es la versión donde los guardias están restringidos a los bordes del polígono. [ 11 ] Además, la mayoría de las otras variaciones estándar (como restringir las ubicaciones de los guardias a los vértices) son NP-difíciles . [ 12 ]

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-difícil , lo que implica que es improbable que se pueda lograr alguna razón de aproximación mejor que alguna constante fija mediante un algoritmo de aproximación de tiempo polinomial . Ghosh (1987) mostró 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 dimensión VC acotada , lo que permite la aplicación de algoritmos de cobertura de conjuntos basados ​​en ε-redes cuya razón de aproximación es el logaritmo del número óptimo de guardias en lugar del número de vértices del polígono. [ 13 ] Para guardias no restringidos, el número infinito de posiciones potenciales de guardia hace que el problema sea aún más difícil. Sin embargo, al restringir que los guardias 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⌊norte/3⌋{\displaystyle \left\lfloor n/3\right\rfloor }guardianes de vértice, que coinciden con la cota superior de Chvátal. David Avis y Godfried Toussaint ( 1981 ) demostraron que la colocación de estos guardianes 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) proporcionaron un algoritmo de tiempo lineal utilizando la breve demostración de Fisk y el algoritmo de triangulación de planos de tiempo lineal de Bernard Chazelle . 

Para polígonos simples que no contienen agujeros, Ghosh conjeturó la existencia de un algoritmo de aproximación de factor constante para guardas de vértice y arista. La conjetura de Ghosh se demostró inicialmente como cierta para guardas de vértice 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 guardas de vértice 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értice. Bhattacharya, Ghosh y Roy (2017) presentaron un algoritmo de aproximación que calcula en tiempo O(n² ) un conjunto de guardas de vértice para un polígono simple que es débilmente visible desde una arista tal que el tamaño del conjunto de guardas es como máximo 6 veces el número óptimo de guardas de vértice. Posteriormente, Bhattacharya, Ghosh y Pal (2017) afirmaron haber resuelto completamente la conjetura al presentar algoritmos de aproximación de factor constante para proteger polígonos simples generales utilizando protecciones de vértice y protecciones de borde. Para proteger los vértices de la subclase de polígonos simples que son débilmente visibles desde un borde, 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 la protección de vértices. Los autores realizaron extensos experimentos computacionales con varias clases de polígonos, demostrando que se pueden encontrar soluciones óptimas en tiempos de cálculo relativamente cortos, 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. [ 14 ]

Tres dimensiones

Un poliedro ortogonal con cada vértice invisible desde su centro [ 15 ]
Un ejemplo de 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 superior 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 , colocar un guardia en cada vértice no garantiza que todo el museo esté bajo vigilancia. Aunque se vigilaría toda la superficie del poliedro, en algunos casos existen puntos en el interior que podrían quedar fuera de vigilancia. [ 16 ]

Aplicaciones

Se han identificado varias aplicaciones del teorema: [ 4 ]

  • Puede ayudar a los museos a iluminar completamente sus galerías.
  • Puede ayudar a los robots móviles a evitar colisiones.
  • Puede garantizar que los artistas en un escenario estén siempre iluminados.
  • Puede utilizarse en zonas urbanas para proporcionar una cobertura completa a transmisores de radio, transceptores de telefonía móvil y detectores de contaminación basados ​​en luz o infrarrojos.
  • En visión artificial, puede ayudar a identificar regiones visibles en una escena.

Véase también

Notas

  1. ↑ Para demostrar la 3-colorabilidad de las triangulaciones de polígonos, observamos que el grafo dual débil de la triangulación (el grafo no dirigido con 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 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 3-coloración por inducción matemática , y esta coloración se extiende fácilmente al vértice adicional del triángulo eliminado. [ 6 ]

Referencias

  1. ↑ O'Rourke (1987) , pág. 1.
  2. ↑ Chvátal (1975) .
  3. ↑ Fisk (1978) .
  4. 1 2 "Robo en el Louvre: ¿Podría un problema matemático de hace 50 años haber mantenido el museo a salvo?" . www.bbc.com . 30 de octubre de 2025.
  5. ↑ Aigner y Ziegler (2018) .
  6. ↑ O'Rourke (1987) , pág. 13.
  7. ^ Shermer (1992) ; Urrutia (2000)
  8. ↑ Kahn, Klawe y Kleitman (1983) ; Lubiw (1985) ; Sack y Toussaint (1988) .
  9. ↑ O'Rourke (1987) , págs. 31–80.
  10. ↑ O'Rourke (1987) , págs. 146–154.
  11. ↑ Abrahamsen, Adamaszek y Miltzow (2022) .
  12. ^ O'Rourke y Supowit (1983) ; Lee y Lin (1986) .
  13. ↑ Brönnimann y Goodrich (1995) .
  14. ↑ Couto, de Rezende & de Souza (2011) .
  15. ↑ Eryk Lipka, Una nota sobre las galerías de arte minimalistas , 2019
  16. ↑ O'Rourke (1987) , pág. 255.

Fuentes

  • Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann (2022), "El problema de las galerías de arte es∃R{\displaystyle \exists {\mathbb {R}}}-completo", Journal of the ACM , 69 (1): A4:1–A4:70, arXiv : 1704.06969 , doi : 10.1145/3486220 , MR 4402363 , S2CID 245059672  
  • 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, MR 3823190 .
  • Ashur, Stav; Filtser, Omrit; Katz, Matthew J.; Saban, Rachel (2019), "Grafos tipo terreno: PTAS para proteger polígonos y terrenos débilmente visibles", en Bampis, Evripidis; Megow, Nicole (eds.), Algoritmos de aproximación y en línea - 17.º Taller Internacional, WAOA 2019, Múnich, Alemania, 12-13 de septiembre de 2019, Artículos seleccionados revisados , Lecture Notes in Computer Science, vol.  11926, Berlín: Springer, pp. 1-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 eficiente para descomponer un polígono en polígonos estrellados" (PDF) , Pattern Recognition , 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 usando protecciones de vértices , arXiv : 1712.05492
  • Bhattacharya, Pritam; Ghosh, Subir Kumar; Roy, Bodhayan (2017), "Aproximabilidad de polígonos de visibilidad débil de vigilancia", 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), "Recubrimientos de conjuntos casi óptimos 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 los guardavuelos 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 en tiempo pseudopolinomial O(logn) para problemas de galerías de arte", Actas del Taller de Algoritmos y Estructuras de Datos , Lecture Notes in Computer Science, vol.  4619, Springer-Verlag, pp. 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 polígonos y terrenos de protección" (PDF) , Algorithmica , 31 (1): 79–113 , doi : 10.1007/s00453-001-0040-8 , S2CID 14532511 , archivado del 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", Actas del 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), "Tricoloración de los vértices de un polígono simple triangulado", Pattern Recognition , 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", Actas del 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 galerías 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-difíciles", 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 guarda en polígonos rectilíneos", en Toussaint, GT (ed.), Morfología computacional , North-Holland, pp . 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), "Problemas de iluminación y galerías de arte", 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), "Guarding galleries where no point sees a small area", Israel Journal of Mathematics , 104 (1): 1– 16, doi : 10.1007/BF02897056.