    Next: What is the Minkowski-Weyl Up: Convex Polyhedron Previous: What is the best   Contents

## What is convex hull? What is the convex hull problem?

For a subset of , the convex hull is defined as the smallest convex set in containing .

The convex hull computation means the determination'' of for a given finite set of points in .

The usual way to determine is to represent it as the intersection of halfspaces, or more precisely, as a set of solutions to a minimal system of linear inequalities. This amounts to output a matrix and a vector for some such that . When is full-dimensional, each (nonredundant) inequality corresponds to a facet of . Thus the convex hull problem is also known as the facet enumeration problem, see Section 2.12.

Some people define the convex hull computation as the determination of extreme points of , or equivalently that of redundant points in to determine . This is much simpler computation than our convex hull problem. In fact, this can be done by solving linear programs and thus polynomially solvable, see Section 2.19 and 2.20. It is better to name this as the redundancy removal for a point set ''.    Next: What is the Minkowski-Weyl Up: Convex Polyhedron Previous: What is the best   Contents
Komei Fukuda 2004-08-26