1988 · 55 citations · 6 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryGeometryConvex GeometryConvex HullsRandomized Geometric AlgorithmsConvex Hull AlgorithmsIntersectionIntersection QueriesLas Vegas AlgorithmsRandomized Convex Hull AlgorithmsRandomized Intersection AlgorithmsRandomized ReductionsSpherical Intersections
We give a simple algorithmic technique for building geometric structures. The technique is randomized and incremental. As an application, we give an algorithm of this kind for computing the intersection of a set of halfspaces in three dimensions. (This intersection problem is linear-time equivalent to the computation of the convex hull of a point set.) The algorithm requires Ο(n log n) expected time, where the expectation is over the random behavior of the algorithm. A similar algorithm can be used to determine the intersection of a set of unit balls in E3, the problem of spherical intersection. This problem arises in the computation of the diameter of a point set in E3. For a set S of n points, the diameter of S is the greatest distance between two points in S. We give a randomized reduction from the problem of determining the diameter to the problem of computing spherical intersections, resulting in a Las Vegas algorithm for the diameter requiring Ο(n log n) expected time. The best algorithms previously known for this problem have worst-case time bounds no better than Ο(n √n log n) [Agg].
6
Computational geometry. an introduction
Franco P. Preparata, Michael Ian Shamos · 1985 · 2.4K citations
Algorithms in Combinatorial Geometry.
Jacob E. Goodman, Herbert Edelsbrunner · American Mathematical Monthly · 1989 · 1.8K citations
Applications of random sampling in computational geometry, II
Kenneth L. Clarkson · 1988 · 943 citations · Full text