Maximización con técnicas metaheurísticas de la región de visibilidad de alcance limitado de un punto en un polígono.

Abstract

El Trabajo Fin de Grado aborda un problema clásico y de gran relevancia en la geometría computacional: encontrar el punto dentro de un polígono simple cuya región de visibilidad, considerando un alcance limitado, sea máxima. Este problema tiene aplicaciones en campos como la robótica, la planificación urbana y la computación gráfica. Dado que el problema es de tipo NP-hard, se opta por utilizar técnicas metaheurísticas para encontrar soluciones aproximadas en tiempos razonables. Concretamente, se emplean tres técnicas: Algoritmo Genético, Simulated Annealing y Búsqueda Tabú, las dos últimas combinadas además con Random Search para mejorar la calidad de las soluciones iniciales. Para facilitar el cálculo del área visible desde un punto, se desarrollan dos nuevos algoritmos que estiman dicha región con complejidades cuadrática y lineal, respectivamente. El estudio incluye la generación aleatoria de 100 polígonos de 25 vértices y una aplicación interactiva que permite visualizar el funcionamiento de los algoritmos. En los experimentos, el Algoritmo Genético obtiene los mejores resultados en términos de área cubierta, pero a costa de un mayor tiempo de ejecución. Por otro lado, Simulated Annealing y Búsqueda Tabú, especialmente cuando se inicializan con Random Search, logran resultados competitivos con tiempos de cómputo más bajos. En conclusión, el trabajo propone una solución eficaz a un problema complejo, desarrollando nuevas herramientas algorítmicas y demostrando que la combinación de búsqueda aleatoria con metaheurísticas locales puede ofrecer un buen equilibrio entre calidad y eficiencia computacional.

The Final Degree Project addresses a classic and highly relevant problem in computational geometry: finding the point inside a simple polygon whose visibility region, considering a limited range, is maximized. This problem has applications in fields such as robotics, urban planning, and computer graphics. Since the problem is NP-hard, metaheuristic techniques are employed to find approximate solutions within reasonable time frames. Specifically, three techniques are used: Genetic Algorithm, Simulated Annealing, and Tabu Search—the latter two combined with Random Search to improve the quality of the initial solutions. To facilitate the calculation of the visible area from a point, two new algorithms are developed with quadratic and linear complexities, respectively. The study includes the random generation of 100 polygons with 25 vertices and an interactive application that allows for visualizing the operation of the algorithms. In the experiments, the Genetic Algorithm achieves the best results in terms of area covered, albeit with a significantly higher execution time. On the other hand, Simulated Annealing and Tabu Search—especially when initialized with Random Search—achieve competitive results with lower computational costs. In conclusion, the project proposes an effective solution to a complex problem by developing new algorithmic tools and demonstrating that combining random search with local metaheuristic techniques can offer a good balance between solution quality and computational efficiency.