# Algorithm to Build Convex Polyhedra

Original Publication Date: 1993-Feb-01

Included in the Prior Art Database: 2005-Mar-18

## Publishing Venue

IBM

## Related People

## Abstract

Disclosed is an algorithm to build a polyhedron from input sets of points and directions. The algorithm is an extension of the Beneath Beyond Method (see [1] chapter 8 for details) to build a polytope (bounded polyhedron) from an input set of points. It had been shown ([2] corollary 7.1b) that any polyhedron P can be represented by P = Q + C where Q is a polytope defined by Q = convex.hull({p[1], . . . , p[k]}) and C = cone({d[1], . . . , d[m]}) where each p[i] is a point and each d[i] is a direction.

**This text was extracted from an ASCII text file.**

**This is the abbreviated version, containing approximately 28% of the total text.**

Algorithm to Build Convex Polyhedra

Disclosed is
an algorithm to build a polyhedron from input sets

of points and directions. The algorithm
is an extension of the

Beneath Beyond Method (see [1] chapter 8
for details) to build a

polytope (bounded polyhedron) from an input set of points. It had

been shown ([2] corollary 7.1b) that any
polyhedron P can be

represented by P = Q + C where Q is a
polytope defined by Q =

convex.hull({p[1], . . . , p[k]}) and C = cone({d[1], . . . , d[m]})

where each p[i] is a point and each d[i]
is a direction.

The input to
the algorithm will be the finite set S = {s[1], .

. . , s[n]} = {p[1], . . . , p[k]}
&union. {d[1], . . . , d[m]},
n

= k + m, p[i] 1 <= i <= k, is a point and d[i] 1 <=
i <= m, is a

direction. At the completion of the
algorithm the generalized

incident graph of the polyhedron P, P = convex.hull({p[1], . . . ,

p[k]}) + cone({d[1], . . . , d[m]}), will be constructed. In

particular the following three sets will be available from the

construction:

o A set of
minimal faces of P.

o A set of directions that defines the
characteristic cone and the

lineality space of P.

o A reduced set of hyperplanes that
define P.

Generalized Incidence Graph

The incident
graph I(Q) of a polytope Q is an undirected graph

whose nodes are in one to one correspondence with the faces of Q, and

I(Q) contains an arc between two nodes if their corresponding faces

are incident [1].

Note: Q is the
only d-dimension face and &Phi. is
the only

Note:

Note:

Note:

(-1)-dimension face.

In order to
extend the incident graph to polyhedra the

following definitions will be required:

1. Let {d[1], . .
., d[k]} be a set of directions
(possibly empty).

The collection L = coll(d[1], . . .,
d[k]) will be defined by: {

d |
d = &sum.
&lambda.[i]od[i] ,
&lambda.[i] <= 0, but not

all &lambda.[i: equal 0 together }
(coll(&Phi.)=&Phi.).

2. Let L =
coll(d[1], . . ., d[k]) then the dimension of L is the

dimension of cone(d[1], . . ., d[k])-1

3. Let L =
coll(d[1], . . ., d[k]) be a collection of dimension k

then L' = coll(d'[1], . . ., d'[j]) is a
sub-collection of L

(and L a super-collection of L') if
and only if: d'[i]

&memberof. {d[1], . . ., d[k]}, 1 <= i <=
j and L' is of

dimension k-1

4. Let f be a
k-face of a d-polyhedron P 1 <= k
<= d and let f = q +

c where q is a polytope and c =
cone(d[1], . . ., d[i]) a cone of

dimension k. The collection L = coll(d'[1], . . ., d'[j])
is a

generalized subface of f (generalized
(k-1)-face of P) if and

only if: d'[&nu.]
&memberof. {d[1], . . .,
d[i]} 1 <= &nu. <=

j, The dimension of L is k-1 and For
all L' = coll(b[1], . . .,

b[r]) if {b[1], . . ., b[r]} &subset.
{d'[1], . . ., d'[j]}

then the dimension of L' is at most k-2.

Note: A generalized (...