ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We use random sampling for several new geometric algorithms. The algorithms are “Las Vegas,” and their expected bounds are with respect to the random behavior of the algorithms. These algorithms follow from new general results giving sharp bounds for the use of random subsets in geometric algorithms. These bounds show that random subsets can be used optimally for divide-and-conquer, and also give bounds for a simple, general technique for building geometric structures incrementally. One new algorithm reports all the intersecting pairs of a set of line segments in the plane, and requiresO(A+n logn) expected time, whereA is the number of intersecting pairs reported. The algorithm requiresO(n) space in the worst case. Another algorithm computes the convex hull ofn points inE d inO(n logn) expected time ford=3, andO(n [d/2]) expected time ford〉3. The algorithm also gives fast expected times for random input points. Another algorithm computes the diameter of a set ofn points inE 3 inO(n logn) expected time, and on the way computes the intersection ofn unit balls inE 3. We show thatO(n logA) expected time suffices to compute the convex hull ofn points inE 3, whereA is the number of input points on the surface of the hull. Algorithms for halfspace range reporting are also given. In addition, we give asymptotically tight bounds for (≤k)-sets, which are certain halfspace partitions of point sets, and give a simple proof of Lee's bounds for high-order Voronoi diagrams.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02187740
Permalink
