Approximating Voronoi Diagrams with Voronoi Diagrams

The tremendous usefulness of Voronoi diagrams is tempered by their worst-case O(n) 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 (Figure 1). We present a new method for constructing approximate Voronoi diagrams that uses the Voronoi diagram of a superset of the input as an approximation to the true Voronoi diagram. The approximate Voronoi cells are unions of Voronoi cells of the superset. If the input has a Voronoi diagram with good aspect ratio (and thus has linear size) then the approximate Voronoi diagramwe produce will simply be the Voronoi diagram of the input. The size of the diagram is O(n log∆) where ∆ is the spread of the input (the ratio of largest to smallest interpoint distances). Moreover, it supports approximate nearest neighbor queries in time O(log∆). We also discuss methods for eliminating the dependence on the spread in the size and reducing it to O(log n) for queries. The construction will be based on sparse meshing technology [4]. Formally, a (1 + e)-approximate Voronoi diagram of an input set N ∈ R is a spatial decomposition of