Menu
I've successfully implemented a way to generate Voronoi diagrams in 2 dimensions using Fortune's method. But now I'm trying to use it for nearest neighbor queries for a point (which is not one of the original points used to generate the diagram). I keep seeing people saying that it can be done in O(lg n) time (and I believe them), but I can't find a description of how it's actually done.
I'm familiar with binary searches, but I can't figure out a good criteria to guarantee that upper bound. I also figured maybe it could have to do with inserting the point into the diagram and updating surrounding cells, but can't think (or find) of a good way to do that.
Can anyone clue me in, or point to a place with a more thorough description?
980
A Voronoi diagram divides a space into disjoint polygons where the nearest neighbor of any point inside a poly- gon is the generator of the polygon.
In hydrology, Voronoi diagrams are used to calculate the rainfall of an area, based on a series of point measurements. In this usage, they are generally referred to as Thiessen polygons.
We start by joining each pair of vertices by a line. We then draw the perpendicular bisectors to each of these lines. These three bisectors must intersect, since any three points in the plane define a circle. We then remove the portions of each line beyond the intersection and the diagram is complete.
I think that some kind of search structure has to be made from plane subdivision (Voronoi diagram), like Kirkpatrick's point location data structure.
78
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
