Convex hulls of finite sets of points in two and three dimensions

1977/02/01 by F. P. Preparata, S. J. Hong · 710 citations
Computer Science · Engineering · Mathematics · #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Convex body #Convex combination #Convex hull #Convex optimization #Convex set #Digital Image Processing Techniques #Discrete mathematics #Divide and conquer algorithms #Engineering #Geometry #Hull #Mathematical analysis #Mathematics #Merge (version control) #Multiplicative function #Orthogonal convex hull #Regular polygon #VLSI and FPGA Design Techniques

paper · pdf · doi:10.1145/359423.359430

published in Communications of the ACM 20(2), 87-93 (Association for Computing Machinery)

openalex publication_date 1977/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

The convex hulls of sets of n points in two and three dimensions can be determined with O(n log n) operations. The presented algorithms use the “divide and conquer” technique and recursively apply a merge procedure for two nonintersecting convex hulls. Since any convex hull algorithm requires at least O(n log n) operations, the time complexity of the proposed algorithms is optimal within a multiplicative constant.

Cited by

• Neural networks for convex hull computation
• Quickhull is Usually Forward Stable
• VQhull: a Fast Planar Quickhull
• CvxNet: Learnable Convex Decomposition
• Online Multivariate Changepoint Detection: Leveraging Links With Computational Geometry
• Existence of a Convex Polyhedron with Respect to the Given Radii
• Divide-and-Conquer 3D Convex Hulls on the GPU
• Self-stabilizing Determinsitic Gathering
• Linear-time algorithms for linear programming in R3 and related problems
• gScan: Accelerating Graham Scan on the GPU
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Voronoi diagrams—a survey of a fundamental geometric data structure
• Bisections and ham-sandwich cuts of convex polygons and polyhedra
• Maintenance of configurations in the plane
• On the convex layers of a planar set
• Applications of random sampling in computational geometry, II
• CudaChain: an alternative algorithm for finding 2D convex hulls on the GPU
• ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE
• The γ-neighborhood graph
• On finding the convex hull of a simple polygon
• Finding minimal enclosing boxes
• Relative neighborhood graphs in the Li-metric
• Linear-Time Algorithms for Linear Programming in R³ and Related Problems
• Applications of random sampling in computational geometry, II
• Some dynamic computational geometry problems
• A Whirlwind Tour of Computational Geometry
• Is evolution of blind mole rats determined by climate oscillations? [europepmc]
• Quantification of Trunk Postural Stability Using Convex Polyhedron of the Time-Series Accelerometer Data. [europepmc]
• CudaChain: an alternative algorithm for finding 2D convex hulls on the GPU. [europepmc]
• A Depth-Adjustment Deployment Algorithm Based on Two-Dimensional Convex Hull and Spanning Tree for Underwater Wireless Sensor Networks. [europepmc]
• Leaf-GP: an open and automated software application for measuring growth phenotypes for arabidopsis and wheat. [europepmc]
• Postural Stability Evaluation of Patients Undergoing Vestibular Schwannoma Microsurgery Employing the Inertial Measurement Unit. [europepmc]
• Segmentation of Multiple Nuclei from Non-overlapping Immuno-histochemically Stained Histological Hepatic Images. [europepmc]
• Pretreatment to terahertz absorption curves by narrow undulation constraint and Its quick implementation suggested by convex hull. [europepmc]
• A novel method for extraction of front boundary agents in multi-agent systems. [europepmc]
• Quantifying Upper Limb Movement During Naturalistic Driving: A Clinically Informed Ecological Approach. [europepmc]

Related

• The quickhull algorithm for convex hulls
• Computing convex hulls and counting integer points with polymake
• Computing the Approximate Convex Hull in High Dimensions
• Convex hull: Incremental variations on the Akl-Toussaint heuristics Simple, optimal and space-saving convex hull algorithms
• A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay Triangulation