Algoritmos que usan el diagrama de Voronoi

Los diagramas de Voronoi fueron por primera vez discutidos por Peter Lejeune-Dirichlet en 1850, pero fue hasta mucho después en 1908 que estos diagramas fueron escritos por Voronoi, de ahí su nombre [RI].

Un diagrama de Voronoi es una estructura geométrica que representa información de proximidad acerca de un conjunto de puntos u objetos es decir, el diagrama de Voronoi de un conjunto de objetos geométricos es una partición del espacio en celdas cada una de la cuales contiene una colindancia con sus puntos más cercanos, obsérvese la figura .

Los diagramas de Voronoi tienen numerosas aplicaciones en diversas áreas que van desde la arqueología hasta la zoología. Por ejemplo, los diagramas de Voronoi son esenciales en la solución de un problema de comunicación sin hilos. Dado un conjunto de subestaciones con n-micro celdas. Cómo pueden ser pre-procesados de modo que para que cualquier llamada celular arbitraria la estación más cercana lleve la llamada?.

Figura: Diagrama de Voronoi para algunos puntos

Los grafos aproximados o diagramas de Voronoi, han sido usados para consultas de proximidad en espacios vectoriales y son una estructura fundamental en la geometría computacional para solucionar el problema de puntos más cercanos. Aunque es realmente un desafío generalizarlo a espacios métricos, porque los algoritmos a construir dependen fuertemente de la información de las coordenadas.