Métodos heurísticos en problemas geométricos. visibilidad, iluminación y vigilancia

Canales Cano, Santiago (2004). Métodos heurísticos en problemas geométricos. visibilidad, iluminación y vigilancia. Thesis (Doctoral), Facultad de Informática (UPM).

Description

Title: Métodos heurísticos en problemas geométricos. visibilidad, iluminación y vigilancia
Author/s:
  • Canales Cano, Santiago
Contributor/s:
  • Abellanas Oar, Manuel
  • Hernández Peñalver, Gregorio
Item Type: Thesis (Doctoral)
Date: 20 September 2004
Subjects:
Freetext Keywords: Visibilidad, Geometría Computacional, Iluminación, Voronoi, Metaheurísticas.
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 (2MB) | Preview

Abstract

Dentro de la Geometría Computacional, uno de los campos que ha suscitado mayor interés entre la comunidad científica internacional ha sido el de la Visibilidad, es decir, el conjunto de problemas que están relacionados con los conceptos de iluminación y vigilancia de estructuras geométricas, con todas sus posibles variantes. Los resultados obtenidos en este ámbito por los investigadores, se pueden aplicar en algunos casos para solucionar problemas industriales reales relacionados con la iluminación o vigilancia,tales como iluminación de calles o de naves comerciales. Sin embargo, en muchas otras ocasiones, los elementos físicos reales que existen en la actualidad, discrepan en algún sentido de los modelos teóricos utilizados, con lo cual los resultados obtenido no son aplicables. Por ello, es necesario utilizar definiciones de visibilidad o iluminación que se acerquen cada vez más a situaciones reales. Siguiendo este objetivo, presentamos en la primera parte de esta memoria resultados combinatorios y algorítmicos utilizando dos definiciones de iluminación que añaden condiciones a los conceptos de vigilancia utilizados tradicionalmente: la primera de estas definiciones fue presentada por Ntafos en 1992, se denomina visibilidad de alcance limitado y añade una restricción a la distancia máxima de iluminación desde un determinado punto; la segunda que hemos denominado t−buena iluminación, se presenta en esta memoria por primera vez y su idea fundamental se basa en que una estructura geométrica sólo está bien iluminada si todos los puntos que la iluminan están bien distribuidos alrededor de ella. Respecto a la visibilidad de alcance limitado presentamos resultados combinatorios para polígonos escalera y polígonos pirámide, mientras para la t−buena iluminación presentamos resultados algoritmos que permiten calcular las regiones iluminadas con esta definición, por luces situadas en diferentes posiciones respecto a un polígono P. Por otra parte existen problemas en el ámbito de la Geometría Computacional que o bien son de naturaleza NP-dura, o bien no se han encontrado hasta el momento algoritmos eficientes que los solucionen. Sin embargo, en ambos casos, puede existir la necesidad real de aportar respuestas a dichos problemas, aunque dichas respuestas sean aproximadas o heurísticas. Así, en la segunda parte de esta memoria, presentamos procedimientos metaheurísticos que abordan problemas con estas características. Esquemáticamente se han abordado dos problemas.El primero de ellos es el problema de minimización del número de luces que iluminan un polígono P, cuya naturaleza NP-dura fue demostrada por Lee y Lin en 1964 y el segundo es el problema de la búsqueda de un nuevo punto en un Diagrama de Voronoi dado, tal que la región asociada a este nuevo punto tenga área máxima en el nuevo Diagrama de Voronoi construido. Para este segundo problema no se han encontrado hasta el momento soluciones algorítmicas eficientes que lo solucionen cuando los puntos se encuentran en posición general, aunque recientemene se han presentado soluciones para puntos situados en posición convexa. Para atacar heurísticamente el primero de estos problemas necesitamos solucionar previamente el problema de la búsqueda del conjunto de k luces, con k ≥ 1, cuyo área conjunta iluminada en el interior de un polígono P sea máxima. Este problema que se analiza por separado para el caso k = 1 y k > 1 constituye el contenido fundamental de la segunda parte de esta memoria.

More information

Item ID: 517
DC Identifier: http://oa.upm.es/517/
OAI Identifier: oai:oa.upm.es:517
Deposited by: D. Santiago Canales Cano
Deposited on: 26 Sep 2007
Last Modified: 20 Apr 2016 06:20
  • 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