** Next:** Is there any efficient
** Up:** Convex Polyhedron
** Previous:** Is there an efficient
** Contents**

##

How can one remove all interior points of from
for large clouds of points in ?

The problem is formally known as the *redundancy removal*.
Let be a set of points in .
We say a point is *redundant* (for ) if
. In short, redundant points are unnecessary
to determine the convex hull .

In principle, one can apply the linear programming (LP)
method given in 2.19
to remove all redundant points. This amounts to solving LPs.
While the time complexity of this pure LP method is polynomial and
additional techniques given by [Cla94,OSS95]
can reduce the size of LPs,
this might end up in
a very time consuming job for large (say ).

There is a technique that might be useful to remove
``obviously redundant'' points quickly as a preprocessing.
This works only in small dimensions (probably up to ?).
Such a method
picks up a few nonredundant point set
from .
Selecting nonredundant points can be done by picking points
maximizing (or minimizing) any given linear function over .
When is small relative to , say or , the computation
of is usually very easy with any standard convex hull
algorithm. Thus we assume that an inequality
system such that
is given.
It is easy to see that any point satisfying
the inequalities (i.e. ) is redundant.
One can repeat the same procedure with a different set
of nonredundant points as long as it removes
``sufficient number'' of redundant points.

** Next:** Is there any efficient
** Up:** Convex Polyhedron
** Previous:** Is there an efficient
** Contents**
Komei Fukuda
2004-08-26