OPTIMIZACIÓN DE LA VIGILANCIA EN ESPACIOS POLIGONALES: EL PROBLEMA DE LA GALERÍA DE ARTE
Authors
Abstract
Este Trabajo de Fin de Grado aborda el problema de la Galería de Arte, un clásico de la geometría computacional que busca determinar el número mínimo de guardias necesarios para vigilar completamente un polígono. El estudio abarca desde fundamentos teóricos de los polígonos hasta la implementación práctica de algoritmos de partición, los cuales simplifican significativamente el análisis de problemas geométricos como el que se analiza en este trabajo.
El trabajo se centra en el problema planteado originalmente por Victor Klee en 1973, explorando los avances teóricos y prácticos desarrollados a lo largo de los años. Se analizan dos algoritmos de partición destacados: el algoritmo de triangulación Ear Clipping, aplicable a polígonos simples con una complejidad temporal cuadrática, y el algoritmo de partición en piezas con forma de L, diseñado específicamente para polígonos ortogonales. Ambos algoritmos se han implementado en Python y se han aplicado a representaciones poligonales de salas del Museo Metropolitano de Arte (MET), modeladas a partir de planos arquitectónicos.
El análisis teórico también destaca la complejidad del problema, clasificado como NP-duro y APX-duro, lo que implica limitaciones para encontrar soluciones óptimas en tiempo polinómico. Esto subraya la importancia de enfoques heurísticos y algoritmos adaptados a la geometría del polígono.
En conclusión, este trabajo combina teoría y práctica para profundizar en el problema de la Galería de Arte, demostrando su relevancia en aplicaciones reales como la vigilancia de espacios arquitectónicos.
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Rey Juan Carlos
URL external
External URL
DOI
Date
Description
Trabajo Fin de Grado leído en la Universidad Rey Juan Carlos en el curso académico 2024/2025. Directores/as: Clara Simón De Blas

