Algoritmo para solucionar el problema inverso generalizado de Voronoi

Dannier Trinchet Almaguer, Hebert Pérez Rosés

Resumen


El presente trabajo se hace un acercamiento a los diagramas de Voronoi, se resuelve uno de los problemas asociados a los diagramas de Voronoi de menos explorados: el Problema Inverso Generalizado de Voronoi. Se presentan los fundamentos teóricos del algoritmo propuesto, dando detalles de diseño, análisis e implementación. Se hace un estudio estadístico para verificar los resultados teóricos esperados, haciendo uso de un generador de entradas aleatorias. El algoritmo recibe como entrada un grafo planar, y devuelve un conjunto de puntos o generadores de Voronoi (sitios). Estos puntos son generados, arista por arista, hasta completar el grafo. Se brindan dos variantes del algoritmo para la generación de los sitios correspondientes a una arista y se realiza una comparación entre ellas. La búsqueda de estos generadores está regida por cierto valor (distancia) dependiente de los ángulos presentes en la subdivisión y las aristas de esta. Como resultado del trabajo se obtuvo un algoritmo, correcto y completo, que encuentra un conjunto minimal de puntos. Se proponen posibles aplicaciones y se hace un análisis de los principales parámetros del algoritmo que influyen en el tamaño del conjunto resultado.


Palabras clave


diagrama de voronoi; geometría computacional; grafo planar; teselación; vecino cercano

Texto completo:

PDF

Enlaces refback

  • No hay ningún enlace refback.




_________________________________________________________________________________________________________

La Universidad de las Ciencias Informáticas (UCI), a través del sello editorial Ediciones Futuro, publica los contenidos de la Revista Cubana de Ciencias Informáticas (RCCI) bajo licencia Creative Commons de tipo Atribución 4.0 Internacional (CC BY 4.0). Esta licencia permite a otros distribuir, mezclar, ajustar y construir a partir de su obra, incluso con fines comerciales, siempre que le sea reconocida la autoría de la creación original.
_________________________________________________________________________________________________________

 INDEXACIÓN