** 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