The quickhull algorithm for convex hulls
Explore this paper's citation graph
Summary
This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull algorithm with the general-dimension Beneath-Beyond Algorithm, and provides empirical evidence that the algorithm runs faster when the input contains nonextreme points and that it used less memory.
- Type
- article
- Published
- 1996-12-01
- Cited by
- 5,792
- References
- 44
- Access
- Open access
- OpenAlex
- https://openalex.org/W2153504150
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:9793096
Keywords
Convex hull, Output-sensitive algorithm, Orthogonal convex hull, Delaunay triangulation, Convex set
References
- Invariant sets for general second-order low-pass delta-sigma modulators with DC inputs
- Automating spectral unmixing of AVIRIS data using convex geometry concepts
- Computational geometry - an introduction through randomized algorithms
- Closed-form solutions to constrained control allocation problem
- Voronoi diagrams—a survey of a fundamental geometric data structure
- A New Convex Hull Algorithm for Planar Sets
- An Algorithm for Convex Polytopes
- Learning in Navigation Goal Finding in Graphs
- The Ultimate Planar Convex Hull Algorithm?
- Construction of three-dimensional Delaunay triangulations using local transformations
- Constructing strongly convex hulls using exact or rounded arithmetic
- Voronoi Diagrams from Convex Hulls
- Convex hulls and isometries of cusped hyperbolic 3-manifolds
- Derandomizing an Output-sensitive Convex Hull Algorithm in Three Dimensions
- Constructing the Convex Hull of a Set of Points in the Plane
- Irregular grain structure in micromagnetic simulation
- Incremental topological flipping works for regular triangulations
- Applications of random sampling in computational geometry, II
- Constructing higher-dimensional convex hulls at logarithmic cost per face
- On the Randomized Construction of the Delaunay Tree
Cited by
- Hierarchical Back-Face Culling
- Indoor Navigation using Approximate Positions
- LP fitting approach for reconstructing parametric surfaces from points clouds
- Pore-Scale Study of the Impact of Fracture and Wettability on Two-Phase Flow Properties of Rock
- Robot path planning : an object-oriented approach
- Construction of 3-D Earth Models for Station Specific Path Corrections by Dynamic Ray Tracing
- Motion planning for manipulators with many degrees of freedom - the BB-method
- Comparing Graph Representations of Protein Structure for Mining Family-Specific Residue-Based Packing Motifs
- Modèle numérique micro-mécanique d'agrégat polycristallin pour le comportement des combustibles oxydes
- Detecting Critical Situation in Public Transport
- Larval Transport Modeling of Deep-Sea Invertebrates Can Aid the Search for Undiscovered Populations
- A spectral analysis of team dynamics and tactics in Brazilian football
- Rapid Human‐Assisted Creation of Bounding Models for Obstacle Avoidance in Construction
- Colorant Selection for Six-Color Lithographic Printing
- New data induced metric for density based clustering
- CRHunter: integrating multifaceted information to predict catalytic residues in enzymes
- Computer Simulations for Hydrogen Loaded Palladium Clusters
- An Algorithm for Approximating the Highest Density Region in d-Space
- Joint Reconstruction of Image and Motion in MRI: Implicit Regularization Using an Adaptive 3D Mesh
- A Cryptic Site of Vulnerability on the Receptor Binding Domain of the SARS-CoV-2 Spike Glycoprotein
Related papers
- An Efficient Convex Hull Algorithm for a Planer Set of Points
- Space subdivision to speed-up convex hull construction in E3
- A Fast Algorithm for Convex Hull of the Planar Points
- DRCH: A Method for 3D Convex Hull
- A novel Q-scanning for convex hull algorithm
- Convex hull calculation approach based on BST
- Robust algorithms for constructing strongly convex hulls in parallel
- A New Algorithm of Minimum Convex Hull and Its Application