file.pdf (101.01 kB)
Download file

Approximating Voronoi Diagrams with Voronoi Diagrams

Download (101.01 kB)
journal contribution
posted on 01.06.2003, 00:00 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

History

Date

01/06/2003

Usage metrics

Exports