Quickhull

Last updated March 19, 2023

Quickhull is a method of computing the convex hull of a finite set of points in n-dimensional space. It uses a divide and conquer approach similar to that of quicksort, from which its name derives. Its worst case time complexity for 2-dimensional and 3-dimensional space is $O(n^{2})$ , 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)$ , where $n$ is the number of input points and $r$ is the number of processed points (up to $n$ ).^[1]

N-dimensional Quickhull was invented in 1996 by C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa.^[1] It was an extension of Jonathan Scott Greenfield's 1990 planar Quickhull algorithm, although the 1996 authors did not know of his methods.^[2] Instead, Barber et al. describe it as a deterministic variant of Clarkson and Shor's 1989 algorithm.^[1]

Algorithm

The 2-dimensional algorithm can be broken down into the following steps:^[2]

Find the points with minimum and maximum x coordinates, as these will always be part of the convex hull. If many points with the same minimum/maximum x exist, use the ones with the minimum/maximum y, respectively.
Use the line formed by the two points to divide the set into two subsets of points, which will be processed recursively. We next describe how to determine the part of the hull above the line; the part of the hull below the line can be determined similarly.
Determine the point above the line with the maximum distance from the line. This point forms a triangle with the two points on the line.
The points lying inside of that triangle cannot be part of the convex hull and can therefore be ignored in the next steps.
Recursively repeat the previous two steps on the two lines formed by the two new sides of the triangle.
Continue until no more points are left, the recursion has come to an end and the points selected constitute the convex hull.

The problem is more complex in the higher-dimensional case, as the hull is built from many facets; the data structure needs to account for that and record the line/plane/hyperplane (ridge) shared by neighboring facets too. For d dimensions:^[1]

Pick d + 1 points from the set that do not share a plane or a hyperplane. This forms an initial hull with facets Fs[].
For each F in Fs[], find all unassigned points that are "above" it; i.e., pointing away from the center of the hull, and assign them to an "outside" set F.O associated with F. The algorithm maintains the invariant that every point that has not been added to the hull but could potentially be a vertex of it is assigned to exactly one outside set.
For each F with a non-empty F.O:
1. Find the point p in F.O with the maximum distance from F and add it to the hull. Note that p will not necessarily be a vertex of the final hull, as it might be removed later.
2. Create a visible set V and initialize it to F. Extend V in all directions for neighboring facets Fv until no further facets are visible from p. Fv being visible from p means that p is above Fv.
3. The boundary of V then forms the set of horizon ridges H.
4. Let Fnew[] be the set of facets created from p and all ridges in H.
5. Unassign all points in the outside sets of facets in V. For each new facet in Fnew[], perform step (2) only considering these newly unassigned points to initialize its outside set. Note that every point that remains unassigned at the end of this process lies within the current hull.
6. Delete the now-internal facets in V from Fs[]. Add the new facets in Fnew[] to Fs[] and continue the iteration.

Pseudocode for 2D set of points

Input = a set S of n points  Assume that there are at least 2 points in the input set S of points  function QuickHull(S) is// Find convex hull from the set S of n points     Convex Hull := {}      Find left and right most points, say A & B, and add A & B to convex hull      Segment AB divides the remaining (n − 2) points into 2 groups S1 and S2          where S1 are points in S that are on the right side of the oriented line from A to B,          and S2 are points in S that are on the right side of the oriented line from B to A      FindHull(S1, A, B)      FindHull(S2, B, A)      Output := Convex Hull end functionfunction FindHull(Sk, P, Q) is// Find points on convex hull from the set Sk of points// that are on the right side of the oriented line from P to QifSk has no point thenreturn     From the given set of points in Sk, find farthest point, say C, from segment PQ      Add point C to convex hull at the location between P and Q      Three points P, Q, and C partition the remaining points of Sk into 3 subsets: S0, S1, and S2          where S0 are points inside triangle PCQ, S1 are points on the right side of the oriented          line from P to C, and S2 are points on the right side of the oriented line from C to Q.      FindHull(S1, P, C)      FindHull(S2, C, Q)  end function

A pseudocode specialized for the 3D case is available from Jordan Smith. It includes a similar "maximum point" strategy for choosing the starting hull. If these maximum points are degenerate, the whole point cloud is as well.^[3]

Related Research Articles

In mathematics and computational geometry, a Delaunay triangulation for a given set $P$ of discrete points in a general position is a triangulation $DT(P)$ such that no point in $P$ is inside the circumcircle of any triangle in $DT(P)$ . Delaunay triangulations maximize the minimum of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

<span class="mw-page-title-main">Simplex</span> Multi-dimensional generalization of triangle

In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. For example,

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.

In computational geometry, the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points.

<span class="mw-page-title-main">Graham scan</span> Algorithm for computing convex hulls in a set of points

Graham's scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(n log n). It is named after Ronald Graham, who published the original algorithm in 1972. The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary efficiently.

In mathematical measure theory, for every positive integer $n$ the ham sandwich theorem states that given $n$ measurable "objects" in $n$ -dimensional Euclidean space, it is possible to divide each one of them in half (with respect to their measure, e.g. volume) with a single $(n - 1)$ -dimensional hyperplane. This is even possible if the objects overlap.

Carathéodory's theorem is a theorem in convex geometry. It states that if a point $lies in the convex hull of a set, then can be written as the convex combination of at most points in . More sharply, can be written as the convex combination of at most extremal points in, as non-extremal points can be removed from without changing the membership of in the convex hull.$

In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that any set of d + 2 points in R^d can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these convex hulls is called a Radon point of the set.

<span class="mw-page-title-main">Convex polytope</span> Convex hull of a finite set of points in a Euclidean space

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the $-dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.$

<span class="mw-page-title-main">Orthogonal convex hull</span> Minimal superset that intersects each axis-parallel line in an interval

In geometry, a set $K \subset R d$ is defined to be orthogonally convex if, for every line $L$ that is parallel to one of standard basis vectors, the intersection of $K$ with $L$ is empty, a point, or a single segment. The term "orthogonal" refers to corresponding Cartesian basis and coordinates in Euclidean space, where different basis vectors are perpendicular, as well as corresponding lines. Unlike ordinary convex sets, an orthogonally convex set is not necessarily connected.

<span class="mw-page-title-main">Chan's algorithm</span> Algorithm for finding the convex hull of a set of points in the plane

In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set $of points, in 2- or 3-dimensional space. The algorithm takes time, where is the number of vertices of the output. In the planar case, the algorithm combines an algorithm with Jarvis march, in order to obtain an optimal time. Chan's algorithm is notable because it is much simpler than the Kirkpatrick-Seidel algorithm, and it naturally extends to 3-dimensional space. This paradigm has been independently developed by Frank Nielsen in his Ph.D. thesis.$

Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.

The smallest-circle problem is a mathematical problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The corresponding problem in n-dimensional space, the smallest bounding sphere problem, is to compute the smallest n-sphere that contains all of a given set of points. The smallest-circle problem was initially proposed by the English mathematician James Joseph Sylvester in 1857.

In mathematics, the vertex enumeration problem for a polytope, a polyhedral cell complex, a hyperplane arrangement, or some other object of discrete geometry, is the problem of determination of the object's vertices given some formal representation of the object. A classical example is the problem of enumeration of the vertices of a convex polytope specified by a set of linear inequalities:

In computational geometry, a CC system or counterclockwise system is a ternary relation $pqr$ introduced by Donald Knuth to model the clockwise ordering of triples of points in general position in the Euclidean plane.

A kinetic convex hull data structure is a kinetic data structure that maintains the convex hull of a set of continuously moving points. It should be distinguished from dynamic convex hull data structures, which handle points undergoing discrete changes such as insertions or deletions of points rather than continuous motion.

In computational geometry, a point $p$ in a finite set of points $S$ is said to be maximal or non-dominated if there is no other point $q$ in $S$ whose coordinates are all greater than or equal to the corresponding coordinates of $p$ . The maxima of a point set $S$ are all the maximal points of $S$ . The problem of finding all maximal points, sometimes called the problem of the maxima or maxima set problem, has been studied as a variant of the convex hull and orthogonal convex hull problems. It is equivalent to finding the Pareto frontier of a collection of points, and was called the floating-currency problem by Herbert Freeman based on an application involving comparing the relative wealth of individuals with different holdings of multiple currencies.

In robust statistics and computational geometry, simplicial depth is a measure of central tendency determined by the simplices that contain a given point. For the Euclidean plane, it counts the number of triangles of sample points that contain a given point.

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

References

1 2 3 4 Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). "The quickhull algorithm for convex hulls" (PDF). ACM Transactions on Mathematical Software. 22 (4): 469–483. doi:10.1145/235815.235821.
1 2 Greenfield, Jonathan S. (1 April 1990). "A Proof for a QuickHull Algorithm". Electrical Engineering and Computer Science - Technical Reports.
↑ Smith, Jordan. "QuickHull 3D". algolist.ru. Retrieved 22 October 2019.

Dave Mount. "Lecture 3: More Convex Hull Algorithms".

External links

Implementing QuickHull (GDC 2014) – Algorithm presentation with 3D implementation details.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Quickhull-1] 1 2 3 4 Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). "The quickhull algorithm for convex hulls" (PDF). ACM Transactions on Mathematical Software. 22 (4): 469–483. doi:10.1145/235815.235821.

[2d-2] 1 2 Greenfield, Jonathan S. (1 April 1990). "A Proof for a QuickHull Algorithm". Electrical Engineering and Computer Science - Technical Reports.

[3] Smith, Jordan. "QuickHull 3D". algolist.ru. Retrieved 22 October 2019.

[1]

[2]

[3]