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