Home Bookmarks Papers Blog

A Replacement for Voronoi Diagrams of Near Linear Size

Sariel Har-Peled

Some Relevant pictures...

Input points
Computing the approximate NN is no more than doing a point-location among prioritized balls. Namely, to find the NN, we find the color in the location of the query point, the corresponding input point with this color is the approximate NN.
Now, we digitize the balls by streaming them into a quadtree. The leafs of the quadtree form the required approximate Voronoi diagram of near-linear complexity. (the white spots on the figure are drawing errors made by drawing library - ignore them).
The figures were generated for epsilon = 0.1. Note that in generating hte quadree we used several simple hueristic to improve the results.
Last updated: Mon May 21 11:25:35 CDT 2001