1988/01/01 by Kenneth L. Clarkson · 5 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Point processes and geometric inequalities #Convex hull #Computational geometry #Mathematics #Combinatorics #Binary logarithm #Algorithm #Las vegas #Regular polygon #Point (geometry) #Plane (geometry) #Simple (philosophy) #Discrete mathematics #Sampling (signal processing) #Computer science #Geometry
paper · pdf · doi:10.1145/73393.73394
openalex publication_date 1988/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
Random sampling is used for several new geometric algorithms. The algorithms are “Las Vegas,” and their expected bounds are with respect to the random behavior of the algorithms. One algorithm reports all the intersecting pairs of a set of line segments in the plane, and requires Ο(A + n log n) expected time, where A is the size of the answer, the number of intersecting pairs reported. The algorithm requires Ο(n) space in the worst case. Another algorithm computes the convex hull of a point set in E3 in Ο(n log A) expected time, where n is the number of points and A is the number of points on the surface of the hull. A simple Las Vegas algorithm triangulates simple polygons in Ο(n log log n) expected time. Algorithms for half-space range reporting are also given. In addition, this paper gives asymptotically tight bounds for a combinatorial quantity of interest in discrete and computational geometry, related to halfspace partitions of point sets.