Nearest Neighbor Searching using Voronoi Diagrams

问题:

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?

回答1:

I think that some kind of search structure has to be made from plane subdivision (Voronoi diagram), like Kirkpatrick's point location data structure.