Nearest Neighbor Searching using Voronoi Diagrams

Question

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?

Beggs

Answer 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.

Dalmatic

That makes sense. I think I'm familiar with that method. I'd upvote you, but I can't yet. – Beggs

@Chad: I haven't been familiar with Kirkpatrick structure until I searched because of your question:-) I worked with Voronoi diagrams before, but I never used them for point location. This method looks quite nice. – Dalmatic