Cloning Voronoi Diagrams via Retroactive Data Structures

Abstract

We address the problem of replicating a Voronoi diagram $V(S)$ of a planar point set $S$ by making proximity queries, which are of three possible (in decreasing order of information content): 1. the exact location of the nearest site(s) in $S$; 2. the distance to and label(s) of the nearest site(s) in $S$; 3. a unique label for every nearest site in $S$. We provide algorithms showing how queries of Type 1 and Type 2 allow an exact cloning of $V(S)$ with $O(n)$ queries and $O(n{\log }^{2}n)$ processing time. We also prove that queries of Type 3 can never exactly clone $V(S)$, but we show that with $O(n\log \frac{1}{\epsilon })$ queries we can construct an $\epsilon$-approximate cloning of $V(S)$. In addition to showing the limits of nearest-neighbor database security, our methods also provide one of the first natural algorithmic applications of retroactive data structures.

More complete version of paper appearing in 2010 European Symposium on Algorithms (ESA)