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

1977/02/01 by F. P. Preparata, S. J. Hong · 17 citations
Computer Science · Engineering · #Digital Image Processing Techniques #Computational Geometry and Mesh Generation #VLSI and FPGA Design Techniques

paper · pdf · doi:10.1145/359423.359430

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
• 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\n Triangulation