Teoremas y algoritmos de la galería de arte

Art Gallery Theorems and Algorithms es una monografía matemática sobre temas relacionados con el problema de la galería de arte , sobre la búsqueda de posiciones para los guardias dentro de un plano poligonal de museo de modo que todos los puntos del museo sean visibles para al menos un guardia, y sobre problemas relacionados en geometría computacional relacionados con polígonos . Fue escrito por Joseph O'Rourke y publicado en 1987 en la Serie Internacional de Monografías sobre Ciencias de la Computación de Oxford University Press . ^{[1] [2] [3] [4] [5]} Solo se produjeron 1000 copias antes de que el libro se agotara, por lo que para mantener este material accesible O'Rourke ha puesto a disposición en línea una versión en pdf del libro. ^[6]

El problema de la galería de arte , planteado por Victor Klee en 1973, pregunta por el número de puntos en los que se deben colocar los guardias dentro de un polígono (que representa el plano de un museo) de modo que cada punto dentro del polígono sea visible para al menos un guardia. Václav Chvátal proporcionó la primera prueba de que la respuesta es como máximo para un polígono con esquinas, pero una prueba simplificada de Steve Fisk basada en la coloración de grafos y la triangulación de polígonos es más conocida. Este es el material de apertura del libro, ^[3] que continúa cubriendo temas que incluyen visibilidad , descomposiciones de polígonos, recubrimientos de polígonos , triangulaciones y algoritmos de triangulación y generalizaciones de dimensiones superiores, ^[1] incluido el resultado de que algunos poliedros como el poliedro de Schönhardt no tienen triangulaciones sin vértices adicionales. ^{[1] [4]} De manera más general, el libro tiene como tema "la interacción entre la geometría discreta y computacional". ^[3]${\displaystyle \lceil n/3\rceil }$${\estilo de visualización n}$

Tiene 10 capítulos, cuyos temas incluyen el teorema original de la galería de arte y la prueba basada en triangulación de Fisk; polígonos rectilíneos ; guardias que pueden patrullar un segmento de línea en lugar de un solo punto; clases especiales de polígonos que incluyen polígonos en forma de estrella , polígonos espirales y polígonos monótonos ; polígonos no simples; problemas del patio de la prisión, en los que los guardias deben ver el exterior, o tanto el interior como el exterior, de un polígono; gráficos de visibilidad ; algoritmos de visibilidad; la complejidad computacional de minimizar el número de guardias; y generalizaciones tridimensionales. ^{[2] [3]}

El libro sólo requiere un conocimiento de nivel de licenciatura de la teoría de grafos y algoritmos . ^[2] Sin embargo, carece de ejercicios y está organizado más como una monografía que como un libro de texto. ^[5] A pesar de advertir que omite algunos detalles que serían importantes para los implementadores de los algoritmos que describe, y no describe algoritmos que funcionen bien con entradas aleatorias a pesar de la poca complejidad del peor caso, el revisor Wm. Randolph Franklin lo recomienda "para la biblioteca de cada geómetra". ^[4]

El crítico Herbert Edelsbrunner escribe que "este libro es la colección más completa de resultados sobre polígonos disponible actualmente y, por lo tanto, se gana su lugar como un texto estándar en geometría computacional. Está muy bien escrito y es un placer leerlo". ^[1] Sin embargo, el crítico Patrick J. Ryan se queja de que algunas de las pruebas del libro son poco elegantes, ^[5] y el crítico David Avis , escribiendo en 1990, señaló que ya en ese momento había "muchos desarrollos nuevos" que hacían que el libro quedara obsoleto. No obstante, Avis escribe que "el libro tiene éxito en varios niveles", como texto introductorio para estudiantes universitarios o para investigadores en otras áreas, y como una invitación a resolver las "muchas preguntas sin resolver" que quedan en esta área. ^[3]