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
(the white spots on the figure are drawing errors made by drawing
library - ignore them).