Quickhull computes the convex hull of a set of points using a divide and conquer strategy similar in spirit to quicksort: it finds the two extreme points on an axis, splits the remaining points into two subsets on either side of the line between them, and recursively finds the farthest point in each subset to build out the hull, discarding points that fall inside the hull as it grows. Average case performance is O(n log n), though a poor choice of splits can degrade it to O(n squared) in the worst case. The technique dates to the 1970s and remains a standard convex hull method taught alongside Graham scan and Jarvis march.
Facts
Partially Attested
Credited ToC. Bradford Barber, David P. Dobkin and Hannu Huhdanpaa (N-dimensional Quickhull, 1996) 1 Wikipedia credits the N-dimensional version to Barber, Dobkin and Huhdanpaa (1996) as an extension of Jonathan Scott Greenfield's 1990 planar algorithm; other literature credits earlier planar work. Time ComplexityO(n squared) worst case in 2 and 3 dimensions; conjectured O(n log r) when input precision is restricted to O(log n) bits 1 Classification
Design Technique Time Complexity
Time Complexity (category)Logarithmic Time -- O(log n) 1 Connections
Credited To
Source Wikipedia: Quickhull
In Field
Source Wikipedia: Quickhull
Invented By
Source Wikipedia: Quickhull
Uses Design Technique
Sources
1. Wikipedia: Quickhull
Lead section, complexity
Its worst case time complexity for 2-dimensional and 3-dimensional space is O(n²), but when the input precision is restricted to O(log n) bits, its worst case time complexity is conjectured to be O(n log r).
History
N-dimensional Quickhull was invented in 1996 by C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa.
entity record, description (design-technique)
Quickhull computes the convex hull of a set of points using a divide and conquer strategy similar in spirit to quicksort: it finds the two extreme points on an axis, splits the remaining points into two subsets on either side of the line between them, and recursively finds the farthest point in each subset to build out the hull, discarding points that fall inside the hull as it grows.
Credited To: David P. Dobkin, Lead
N-dimensional Quickhull was invented in 1996 by C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa.
- In Field: Algorithms and Complexity Theory, Lead paragraph
In Group: Convex Hull Algorithms, Lead section
method of computing the convex hull of a finite set of points
Invented By: David P. Dobkin, Lead
N-dimensional Quickhull was invented in 1996 by C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.