Browse Prior Art Database

Algorithm to Build Convex Polyhedra

IP.com Disclosure Number: IPCOM000103836D
Original Publication Date: 1993-Feb-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 4 page(s) / 166K

Publishing Venue

IBM

Related People

Golan, I: AUTHOR

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 (...