Approximating Voronoi Diagrams with Voronoi Diagrams

The tremendous usefulness of Voronoi diagrams is tempered by their worst-case O(n⌈d/2⌉) size blowup. This makes them an obvious target for approximation, and indeed, several methods have been proposed that produce linear size approximations to the Voronoi diagram supporting logarithmic-time approximate nearest neighbor queries. All such methods use quadtrees to approximate the Voronoi cells. But what if the input does not have a “bad” Voronoi diagram? There is a huge gap between the best-case and the worst case complexity. Sometimes, the exact solution is both simpler and more precise than an approximatio