Polígono de visibilidad desde un lado

Abstract

El algoritmo central que se trata en este trabajo es el presentado por Lee y Lin (1986) para calcular V(a,b). En el trabajo desarrollamos una implementación de dicho algoritmo de complejidad O(n log n). Para ello nos apoyamos en una estructura de datos llamada (Aho, Hopcroft y Ullman 1974) cola concatenable, para la cual desarrollamos una implementación particular que hemos llamado árbol-pila binario. Desarrollamos una segunda implementación para la cola concatenable con una lista para poder mostrar los estados intermedios del algoritmo y poder analizarlo paso a paso. Esta segunda implementación al realizar búsquedas secuenciales en lugar de binarias eleva la complejidad del algoritmo total a O(n2). Presentamos un algoritmo para calcular el polígono de visibilidad desde un vértice, basado en el algoritmo de Lee y Lin para un lado. Este algoritmo tiene complejidad lineal. Implementamos igualmente este algoritmo basándonos en la implementación anterior para un lado. Por último hemos desarrollado un algoritmo para pasar un polígono a forma estándar.