The nearest neighboring areas are visualized.

Question

I am writing an application that searches for points in two-dimensional space using the kd tree . It would be nice, during development, to be able to "see" the zones of the nearest neighbor surrounding each point.

In the attached image, the red points are points in the kd tree, and the blue lines surrounding each point connect the area in which the search for the nearest neighbor returns the contained point.

The image was created in this way:

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 importantly) This is my slow (reasonably fast Core i7) computer.
• (less important) This is careless, as you can see from the different widths of the blue lines.

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

What are some good algorithms for creating such a visualization?

Answer 1

This is called the Voronoi Diagram , and there are many excellent algorithms for creating them efficiently. The one I have heard about the most is the Fortune algorithm , which works in O (n log n) time, although there are other algorithms for this problem.

Hope this helps!

Answer 2

Jacob,

Hey, you found an interesting way to generate this Voronoi diagram, although it is not so efficient.

A less important question in the first place: the different boundaries of the borders that you get, these forms of butterflies, are actually the area between the two branches of the hyperbola. It is the hyperbola given by the equation | da - db | = 4. To get a thick line instead, you must change this criterion and replace it with the distance to the bisector of the two nearest neighbors, let A and B; using vector calculus, | PA.AB / || AB || - || AB || / 2 | <4.

More important issue: there are two well-known effective solutions for constructing a Voronoi diagram for many points: the Fortune sweep algorithm (as mentioned by templatetypedef) and the Preptata and Shamos Divide and Conquer solutions. Both work at the optimal time O (N.Lg (N)) for N points, but they are not so simple to implement.

This algorithm constructs a Voronoi diagram as a set of segments and half-straight lines. Check out http://en.wikipedia.org/wiki/Voronoi_diagram .

This article, “Primitives for Manipulating Common Units and Voronoi’s Computing,” describes both algorithms using a somewhat higher-level structure, taking care of all the implementation details; the article is complicated, but the algorithms are feasible.

You can also take a look at the “simple iterative algorithm for the Voronoi planar diagram”, which I have never tried.

A completely different approach is to directly construct a distance map from these points, for example, using the Dijkstra algorithm: starting from these points, you increase the boundary of the region at a given distance from each point and stop growing when two boundaries meet. [More explanation required.] See http://1.bp.blogspot.com/-O6rXggLa9fE/TnAwz4f9hXI/AAAAAAAAAPk/0vrqEKRPVIw/s1600/distmap-20-seed4-fin.jpg

Another good starting point (for efficiently calculating distance maps) could be the "General Algorithm for Calculating Distance in Linear Time."

Answer 3

From personal experience: the luck algorithm is a pain that needs to be implemented. The separation and submission algorithm presented by Guibas and Stolfi is not so bad; they give a detailed pseudo-code that is easily written into a procedural programming language. Both will explode if you have almost degenerate inputs and use floating points, but since primitives are quadratic, if you can represent the coordinates as 32-bit integers, then you can use 64 bits to perform determinant calculations.

Once you earn it, you might consider replacing your kd-tree algorithms, which have Theta (√n) worst case, with algorithms that work on planar units.

Answer 4

You can find a great implementation for it in the D3.js library: http://mbostock.github.com/d3/ex/voronoi.html