Nearest neighbor zones visualized

Question

I'm writing an app that looks up points in two-dimensional space using a k-d tree. It would be nice, during development, to be able to "see" the nearest-neighbor zones surrounding each point.

In the attached image, the red points are points in the k-d tree, and the blue lines surrounding each point bound the zone where a nearest neighbor search will return the contained point.

The image was created thusly:

for each point in the space:
  da = distance to nearest neighbor
  db = distance to second-nearest neighbor
  if absolute_value(da - db) < 4:
    draw blue pixel

This algorithm has two problems:

• (more important) It's slow on my (reasonably fast Core i7) computer.
• (less important) It's sloppy, as you can see by the varying widths of the blue lines.

What is this "visualization" of a set of points called?

What are some good algorithms to create such a visualization?

Answer 1

This is called a Voronoi Diagram and there are many excellent algorithms for generating them efficiently. The one I've heard about most is Fortune's algorithm, which runs in time O(n log n), though others algorithms exist for this problem.

Hope this helps!