Editing Convex hull (section)

==Computation==
{{Main article|Convex hull algorithms}}

In [[computational geometry]], a number of algorithms are known for computing the convex hull for a finite set of points and for other geometric objects.
Computing the convex hull means constructing an unambiguous, efficient [[data structure|representation]] of the required convex shape. Output representations that have been considered for convex hulls of point sets include a list of [[linear inequality|linear inequalities]] describing the [[Facet (geometry)|facets]] of the hull, an [[undirected graph]] of facets and their adjacencies, or the full [[face lattice]] of the hull.{{sfnp|Avis|Bremner|Seidel|1997}} In two dimensions, it may suffice more simply to list the points that are vertices, in their cyclic order around the hull.{{sfnp|de Berg|van Kreveld|Overmars|Schwarzkopf|2008|page=3}}

For convex hulls in two or three dimensions, the complexity of the corresponding algorithms is usually estimated in terms  of <math>n</math>, the number of input points, and <math>h</math>, the number of points on the convex hull, which may be significantly smaller than <math>n</math>. For higher-dimensional hulls, the number of faces of other dimensions may also come into the analysis. [[Graham scan]] can compute the convex hull of <math>n</math> points in the plane in time <math>O(n\log n)</math>. For points in two and three dimensions, more complicated [[output-sensitive algorithm]]s are known that compute the convex hull in time <math>O(n\log h)</math>. These include [[Chan's algorithm]] and the [[Kirkpatrick–Seidel algorithm]].{{sfnp|de Berg|van Kreveld|Overmars|Schwarzkopf|2008|page=13}} For dimensions <math>d>3</math>, the time for computing the convex hull is <math>O(n^{\lfloor d/2\rfloor})</math>, matching the worst-case output complexity of the problem.<ref>{{harvtxt|Chazelle|1993}}; {{harvtxt|de Berg|van Kreveld|Overmars|Schwarzkopf|2008}}, p. 256.</ref> The convex hull of a simple polygon in the plane can be constructed in [[linear time]].<ref>{{harvtxt|McCallum|Avis|1979}}; {{harvtxt|Graham|Yao|1983}}; {{harvtxt|Lee|1983}}.</ref>

[[Dynamic convex hull]] data structures can be used to keep track of the convex hull of a set of points undergoing insertions and deletions of points,{{sfnp|Chan|2012}} and [[kinetic convex hull]] structures can keep track of the convex hull for points moving continuously.{{sfnp|Basch|Guibas|Hershberger|1999}}
The construction of convex hulls also serves as a tool, a building block for a number of other computational-geometric algorithms such as the [[rotating calipers]] method for computing the [[width]] and [[Diameter (computational geometry)|diameter]] of a point set.{{sfnp|Toussaint|1983}}