Art Gallery Theorems and Algorithms es una monografía matemática sobre temas relacionados con el problema de la galería de arte , sobre cómo encontrar posiciones para los guardias dentro de un plano poligonal de un museo para que todos los puntos del museo sean visibles para al menos un guardia, y sobre problemas relacionados en geometría computacional. sobre 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 la 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 creado una versión en pdf del libro disponible en línea. [6]
Temas
El problema de la galería de arte , planteado por Victor Klee en 1973, pide el número de puntos en los que colocar guardias dentro de un polígono (que representa el plano de un museo) para 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 coloración de gráficos y triangulación de polígonos es más conocida. Este es el material de apertura del libro, [3] que pasa a cubrir temas que incluyen visibilidad , descomposición de polígonos, cobertura de polígonos , triangulaciones y algoritmos de triangulación, y generalizaciones de dimensiones superiores, [1] incluido el resultado de que algunos poliedros como como el poliedro de Schönhardt no tiene 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]
Tiene 10 capítulos, cuyos temas incluyen el teorema de la galería de arte original 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 en espiral 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]
Audiencia y recepción
El libro solo requiere un conocimiento de nivel universitario de 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 los algoritmos que funcionan bien en entradas aleatorias a pesar de la pobre complejidad del peor de los casos, el revisor Wm. Randolph Franklin lo recomienda "para la biblioteca de todo 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, gana su lugar como 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 de los libros no son elegantes, [5] y el crítico David Avis , que escribió en 1990, señaló que ya en ese momento había "muchos desarrollos nuevos" que hacían que el libro fuera obsoleto. Sin embargo, Avis escribe que "el libro tiene éxito en varios niveles", como texto introductorio para estudiantes universitarios o para investigadores de otras áreas, y como una invitación a resolver las "muchas cuestiones sin resolver" que quedan en esta área. [3]
Referencias
- ^ a b c d Edelsbrunner, Herbert (1989), "Revisión de los teoremas y algoritmos de la galería de arte ", Revisiones matemáticas , MR 0921437
- ^ a b c Vlach, M., "Revisión de los teoremas y algoritmos de la galería de arte ", zbMATH , Zbl 0653.52001
- ^ a b c d e Avis, David (1990), "Review of Art Gallery Theorems and Algorithms ", American Mathematical Society , New Series, 23 (1): 230-234, doi : 10.1090 / S0273-0979-1990-15939-7 , MR 1567872
- ^ a b c Franklin, Wm. Randolph (junio de 1989), "Review of Art Gallery Theorems and Algorithms ", SIAM Review , 31 (2): 342–343, doi : 10.1137 / 1031076
- ^ a b c Ryan, Patrick J., "Revisión de los teoremas y algoritmos de la galería de arte " , Reseñas de computación de ACM
- ^ O'Rourke, Joseph , Art Gallery Theorems and Algorithms , Smith College , consultado el 20 de febrero de 2020.