Applications of random sampling in computational geometry, II

1989/10/01 by Kenneth L. Clarkson, Peter W. Shor · 4 citations
Computer Science · Mathematics · #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computational geometry #Convex body #Convex hull #Convex optimization #Convex set #Data Management and Algorithms #Discrete mathematics #Geometry #Intersection (aeronautics) #Mathematics #Output-sensitive algorithm #Point processes and geometric inequalities #Regular polygon #Voronoi diagram

paper · pdf · doi:10.1007/bf02187740

crossref issued 1989/10/01 · crossref published 1989/10/01 · crossref published-online 1989/10/01 · crossref published-print 1989/10/01 · openalex publication_date 1989/10/01 · crossref created 2005/09/20 · crossref deposited 2020/04/09 · openalex created_date 2025/10/10 · crossref indexed 2026/03/26 · openalex updated_date 2026/07/23

Citations

• Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension
• A fast las vegas algorithm for triangulating a simple polygon
• Linear Programming in Linear Time When the Dimension Is Fixed
• Halfspace range search: An algorithmic application ofk-sets
• The number of small semispaces of a finite set of points in the plane
• On k-Hulls and Related Problems
• Convex hulls of finite sets of points in two and three dimensions
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• The power of geometric duality
• Constructing Arrangements of Lines and Hyperplanes with Applications
• On the shape of a set of points in the plane

Cited by

• Construction of ɛ-nets
• Incremental topological flipping works for regular triangulations
• Voronoi diagrams—a survey of a fundamental geometric data structure
• K-set (geometry) [wikipedia]