Carnegie Mellon University
file.pdf (101.01 kB)

Approximating Voronoi Diagrams with Voronoi Diagrams

Download (101.01 kB)
journal contribution
posted on 2003-06-01, 00:00 authored by Gary L. Miller, Todd Phillips, Donald Sheehy
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 approximation




Usage metrics