Let S be a set of points in E^d, in general position,
so that no d+1 points of S are in a common hyperplane.
Suppose we want to find the vertices of the convex hull of S,
the extreme points of S.
Consider the following algorithm:
E := {};
for each p in S do
If p is in E, skip it.
Check if p is in conv(E);
If p is not in conv(E) then
use the proof that p is not in conv(E)
to find v in vert(conv(S))\E, and add v to E.
od;
-
Show that this algorithm can be implemented to run in O(nV) expected time,
where V is the size of vert(conv(S)). Hint: use linear programming
to find the "proof".
- For p in S, define depth(p, S) as 1 if p is an extreme point of S, so
p is in vert(conv(S)),
and otherwise depth(p, S) is 1+depth(p, S\vert(conv(S))).
Show that the depth of every point in S can be computed in O(n2)
expected time.
-
Given a set H of n hyperplanes, a halfspace h is called irredundant
if P(H) is not equal to P(H\{h}). Show that a halfspace can be proven
irredundant in O(n) expected time. Show that the I irredundant halfspaces
of H can be found in O(nI) expected time.
- Each irredundant halfspace of H determines a facet of P(H).
Recall that a face of a polyhedron is either a facet, or a face of
a facet.
Show that all F faces of P(H) can be found in O(nF) expected time
and O(n) space. The "constant factors" in O( ) may be exponential in d.