Cloning Voronoi Diagrams via Retroactive Data Structures

Details Cloning Voronoi Diagrams via Retroactive Data Structures Cloning Voronoi Diagrams via Retroactive Data Structures

2010-06-09

arxiv.org/abs/1006.1921v1

Computer Science

Computational Geometry

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Cloning Voronoi Diagrams via Retroactive Data Structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cloning Voronoi Diagrams via Retroactive Data Structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cloning Voronoi Diagrams via Retroactive Data Structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-490344