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.
Motivated by the problem of having a robot discover the shape of an object by touching it @cite_22 , there is considerable amount of related work in the computational geometry literature on discovering polygonal and polyhedral shapes from probing (e.g., see @cite_9 @cite_29 @cite_43 @cite_1 @cite_12 @cite_3 @cite_4 @cite_26 @cite_41 @cite_34 ). Rather than review all of this work in detail, we (e.g., see @cite_9 @cite_29 @cite_1 @cite_12 @cite_3 @cite_4 @cite_41 @cite_34 ). We refer the interested reader to the survey and book chapter by Skiena @cite_18 @cite_13 , and simply mention that, with the notable exception of work by Dobkin @cite_12 , this prior work is primarily directed at discovering obstacles in a two-dimensional environment using various kinds of contact probes. Thus, although it is related, most of this prior work cannot be adapted to the problem of discovering a Voronoi diagram through nearest-neighbor probes.
@cite_18 @cite_26 @cite_4 @cite_22 @cite_41 @cite_9 @cite_29 @cite_1 @cite_3 @cite_43 @cite_34 @cite_13 @cite_12
1968632103 2026732056 2088549534 1973492835 2153050879 2015816463 1590151786 2038334420 2073564310 1995282992 1972923728
A testing algorithm takes a model and produces a set of points that can be used to test whether or not an unknown object is sufficiently similar to the model. A testing algorithm performs a complementary task to that performed by a learning algorithm, which takes a set of examples and builds a model that succinctly describes them. Testing can also be viewed as a type of geometric probing that uses point probes (i.e. test points) to verify that an unknown geometric object is similar to a given model. In this paper we examine the problem of verifying orthogonal shapes using test points. In particular, we give testing algorithms for sets of disjoint rectangles in two and higher dimensions and for general orthogonal shapes in 2-D and 3-D. This work is a first step towards developing efficient testing algorithms for objects with more general shapes, including those with non-orthogonal and curved surfaces. Abstract We prove that n+4 finger probes are sufficient to determine the shape of a convex n-gon from a finite collection of models, improving the previous result of 2n+1. Further, we show that n−1 are necessary, proving this is optimal to within an additive constant. For line probes, we show that 2n+4 probes are sufficient and 2n−3 necessary. The difference between these results is particularly interesting in light of the duality relationship between finger and line probes. We consider a new problem motivated by robotics: how to determine shape and position from probes. We show that 3n probes are sufficient, but 3n − 1 are necessary, to determine the shape and position of any n-gon. Under a mild assumption, 3n probes are necessary. Geometric probing considers problems of determining a geometric structure or some aspect of that structure from the results of a mathematical or physical measuring device, a probe. The field of geometric probing is surveyed, with results ordered by a probing model. The emphasis is on interactive reconstruction, where the results of all previous measurements are used to determine the orientation of the next probe so it provides the maximum amount of information about the structure. Through interactive reconstruction, finite determination strategies exist for such diverse models as finger, X-ray, and half-plane probes. > We present algorithms to reconstruct the planar cross-section of a simply connected object from data points measured by rays. The rays are semi-infinite curves representing, for example, the laser beam or the articulated arms of a robot moving around the object. This paper shows that the information provided by the rays is crucial (though generally neglected) when solving 2-dimensional reconstruction problems. The main property of the rays is that they induce a total order on the measured points. This order is shown to be computable in optimal time O(n log n). The algorithm is fully dynamic and allows the insertion or the deletion of a point in O(log n) time. From this order a polygonal approximation of the object can be deduced in a straightforward manner. However, if insufficient data are available or if the points belong to several connected objects, this polygonal approximation may not be a simple polygon or may intersect the rays. This can be checked in O(n log n) time. The order induced by the rays can also be used to find a strategy for discovering the exact shape of a simple (but not necessarily convex) polygon by means of a minimal number of probes. When each probe outcome consists of a contact point, a ray measuring that point and the normal to the object at the point, we have shown that 3n-3 probes are necessary and sufficient if the object has n non-colinear edges. Each probe can be determined in O(log n) time yielding an O(n log n)-time 0(n)-space algorithm. When each probe outcome consists of a contact point and a ray measuring that point but not the normal, the same strategy can still be applied. Under a mild condition, 8n-4 probes are sufficient to discover a shape that is almost surely the actual shape of the object. Suppose that for a set H of n unknown hyperplanes in the Euclidean d-dimensional space, a line probe is available which reports the set of intersection points of a query line with the hyperplanes. Under this model, this paper investigates the complexity to find a generic line for H and further to determine the hyperplanes in H. This problem arises in factoring the u-resultant to solve systems of polynomials (e.g., Renegar [13]). We prove that d+1 line probes are sufficient to determine H. Algorithmically, the time complexity to find a generic line and reconstruct H from O(dn) probed points of intersection is important. It is shown that a generic line can be computed in O(dn log n) time after d line probes, and by an additional d line probes, all the hyperplanes in H are reconstructed in O(dn log n) time. This result can be extended to the d-dimensional complex space. Also, concerning the factorization of the u-resultant using the partial derivatives on a generic line, we touch upon reducing the time complexity to compute the partial derivatives of the u-resultant represented as the determinant of a matrix. An X-ray probe through a polygon measures the length of intersection between a line and the polygon. This paper considers the properties of various classes of X-ray probes, and shows how they interact to give finite strategies for completely describing convex n-gons. It is shown that @math probes are sufficient to verify a specified n-gon, while for determining convex polygons @math X-ray probes are necessary and @math sufficient, with @math sufficient given that a lower bound on the size of the smallest edge of P is known. Abstract Let Γ be a set of convex unimodal polygons in fixed position and orientation. We prove that the problem of determining whether k finger probes are sufficient to distinguish among the polygons in Γ is NP-complete for two types of finger probes. This implies that the same results hold for most interesting classes of polygons on which finger probes can be used. 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.