Implementé correctamente una forma de generar diagramas de Voronoi en 2 dimensiones utilizando el método de Fortune. Pero ahora estoy tratando de usarlo para consultas vecinas más cercanas para un punto (que no es uno de los puntos originales utilizados para generar el diagrama). Sigo viendo gente diciendo que se puede hacer en el tiempo O (lg n) (y yo les creo), pero no puedo encontrar una descripción de cómo se hace realmente.Búsqueda de vecino más cercano utilizando diagramas de Voronoi
Estoy familiarizado con las búsquedas binarias, pero no puedo encontrar un buen criterio para garantizar ese límite superior. También pensé que tal vez tendría que ver con insertar el punto en el diagrama y actualizar las celdas circundantes, pero no puedo pensar (o encontrar) una buena manera de hacerlo.
¿Alguien puede darme una pista o señalar un lugar con una descripción más detallada?
Eso tiene sentido. Creo que estoy familiarizado con ese método. Te hubiera votado, pero todavía no puedo. –
@Chad: No he estado familiarizado con la estructura de Kirkpatrick hasta que busqué debido a su pregunta :-) Trabajé con diagramas de Voronoi antes, pero nunca los usé para la ubicación de los puntos. Este método se ve bastante bien. – Ante