Polígono de visibilidad desde un lado

González Díaz-Carralero, Alberto Isidro (2009). Polígono de visibilidad desde un lado. Proyecto Fin de Carrera / Trabajo Fin de Grado, Facultad de Informática (UPM).

Description

Title: Polígono de visibilidad desde un lado
Author/s:
  • González Díaz-Carralero, Alberto Isidro
Contributor/s:
  • Hernández Peñalver, Gregorio
Item Type: Final Project
Date: 7 July 2009
Subjects:
Freetext Keywords: Geometría Computacional, Visibilidad, Cola Concatenable, Polígono en Forma Estándar, Polígono de Visibilidad desde un Punto, Polígono de Visibilidad desde un Lado
Faculty: Facultad de Informática (UPM)
Department: Matemática Aplicada
Creative Commons Licenses: Recognition - Non commercial - Share

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (791kB) | Preview

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.

More information

Item ID: 1736
DC Identifier: http://oa.upm.es/1736/
OAI Identifier: oai:oa.upm.es:1736
Deposited by: Sr. Alberto Isidro González Díaz-Carralero
Deposited on: 09 Jul 2009
Last Modified: 20 Apr 2016 06:58
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM