We address the problem of replicating a Voronoi diagram @math of a planar point set @math 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 @math ; 2. the distance to and label(s) of the nearest site(s) in @math ; 3. a unique label for every nearest site in @math . We provide algorithms showing how queries of Type 1 and Type 2 allow an exact cloning of @math with @math queries and @math processing time. We also prove that queries of Type 3 can never exactly clone @math , but we show that with @math queries we can construct an @math -approximate cloning of @math . 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.
By a well-known lifting method (e.g., see @cite_40 ), a 2-dimensional Voronoi diagram can be defined by a projection to the plane of the skeleton of a 3-dimensional convex polyhedron, which is defined by the upper envelope of planes tangent at point sites mapped vertically to a certain paraboloid. This property of Voronoi diagrams implies that the method of Dobkin @cite_12 for discovering a convex polytope via ray-shooting finger'' probes can be used to discover a Voronoi diagram in the plane using nearest-neighbor queries (for instance, the queries we call exact queries''). Translated into this context, their method results in a scheme that would use @math queries to clone a Voronoi diagram, with a time overhead that is @math .
@cite_40 @cite_12
2149906774 1972923728
This introduction to computational geometry focuses on algorithms. Motivation is provided from the application areas as all techniques are related to particular applications in robotics, graphics, CAD CAM, and geographic information systems. Modern insights in computational geometry are used to provide solutions that are both efficient and easy to understand and implement. We investigate the complexity of determining the shape and presentation (i.e. position with orientation) of convex polytopes in multi-dimensional Euclidean space using a variety of probe models.