Item type: Item , Access status: Restricted , Add to my list

OPTIMIZACIÓN DE LA VIGILANCIA EN ESPACIOS POLIGONALES: EL PROBLEMA DE LA GALERÍA DE ARTE

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

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

Citation

Endorsement

Review

Supplemented By

Referenced By

Statistics

Views
1
Downloads
0

Bibliographic managers