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

摘要: Dentro de la Geometria Computacional, uno los campos que ha suscitado mayor interes entre comunidad cientifica internacional sido el Visibilidad, es decir, conjunto problemas estan relacionados con conceptos iluminacion y vigilancia estructuras geometricas, todas sus posibles variantes. Los resultados obtenidos en este ambito por investigadores, se pueden aplicar algunos casos para solucionar industriales reales o vigilancia,tales como calles naves comerciales. Sin embargo, muchas otras ocasiones, elementos fisicos existen actualidad, discrepan algun sentido modelos teoricos utilizados, lo cual obtenido no son aplicables. Por ello, necesario utilizar definiciones visibilidad acerquen cada vez mas a situaciones reales. Siguiendo objetivo, presentamos primera parte esta memoria combinatorios algoritmicos utilizando dos anaden condiciones utilizados tradicionalmente: estas fue presentada Ntafos 1992, denomina alcance limitado anade una restriccion distancia maxima desde un determinado punto; segunda hemos denominado t-buena iluminacion, presenta su idea fundamental basa estructura geometrica solo bien iluminada si todos puntos iluminan distribuidos alrededor ella. Respecto poligonos escalera piramide, mientras algoritmos permiten calcular las regiones iluminadas definicion, luces situadas diferentes posiciones respecto poligono P. Por otra Computacional naturaleza NP-dura, han encontrado hasta momento eficientes solucionen. ambos casos, puede existir necesidad real aportar respuestas dichos problemas, aunque dichas respuestas sean aproximadas heuristicas. Asi, memoria, procedimientos metaheuristicos abordan caracteristicas. Esquematicamente abordado problemas.El primero ellos problema minimizacion del numero poligono P, cuya NP-dura demostrada Lee Lin 1964 segundo busqueda nuevo punto Diagrama Voronoi dado, tal region asociada tenga area construido. Para soluciones algoritmicas solucionen cuando encuentran posicion general, recientemene presentado situados convexa. Para atacar heuristicamente estos necesitamos previamente k luces, = 1, cuyo area conjunta interior P sea maxima. Este analiza separado caso 1 > constituye contenido memoria.