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. Tesis (Doctoral), Facultad de Informática (UPM) [antigua denominación].

Descripción

Título: Métodos heurísticos en problemas geométricos. visibilidad, iluminación y vigilancia
Autor/es:
  • Canales Cano, Santiago
Director/es:
  • Abellanas Oar, Manuel
  • Hernández Peñalver, Gregorio
Tipo de Documento: Tesis (Doctoral)
Fecha: 20 Septiembre 2004
Materias:
Palabras Clave Informales: Visibilidad, Geometría Computacional, Iluminación, Voronoi, Metaheurísticas.
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Matemática Aplicada
Licencias Creative Commons: Reconocimiento - No comercial - Compartir igual

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (2MB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 517
Identificador DC: http://oa.upm.es/517/
Identificador OAI: oai:oa.upm.es:517
Depositado por: D. Santiago Canales Cano
Depositado el: 26 Sep 2007
Ultima Modificación: 20 Abr 2016 06:20
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM