Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Direct Polyhedron Projection Algorithm

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

Publishing Venue

IBM

Related People

Golan, I: AUTHOR

Abstract

Disclosed is an algorithm to compute the projection of a polyhedron. Given Q a d-dimensional polyhedron defined by a set of constraints Q= {x | A*x <= b} and X the sub-space defined by {x[1], . . . , x[k]} a set of coordinates (k <= d), the projection ( Q[x] ) of the polyhedron Q on X is generated.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 23% of the total text.

Direct Polyhedron Projection Algorithm

      Disclosed is an algorithm to compute the projection of a
polyhedron.  Given Q a d-dimensional polyhedron defined by a set of
constraints Q= {x | A*x <=  b}  and X the sub-space defined by {x[1],
. . . , x[k]}  a set of coordinates (k <=  d), the projection ( Q[x]
) of the polyhedron Q on X is generated.

      The behavior of the known algorithms, usually a variation on
the extreme points evaluations or Fourier elimination method, depends
heavily on the size and form of the input [6].  Frequently due to the
generation of a huge intermediate data, or extremely time-consuming
procedures (i.e., redundancy checks), the algorithms do not produce
an answer (or even a partial result) in cases where the size of the
output is small.  In the algorithm presented here the amount of
computations depends more on the size of the output (the convex hull
algorithm part) than on the size of the input (the linear programming
part).  The effect on the length of the computation in case the input
set of constraints is redundant, is not critical.  Moreover, if the
size of the output and/or time limitation precludes finding the
complete answer, an approximation can be produced and a measure of
"closeness" can be evaluated.

      The algorithm builds the projection of Q on X incrementally by
finding extreme points and rays of Q[x].  Extreme points are found by
successively finding new support hyperplane of Q that are also
support hyperplane of Q[x].  These are support hyperplanes of Q that
are perpendicular to the subspace X.  Possible directions of the cone
included in Q[x]  (in case Q[x]  is unbounded) are found by checking
appropriate edges of the already existing part of the projection (see
-- Heading 'CHECK' unknown --).  An algorithm based on a similar idea
appeared in [3].  However it was restricted to the bounded case and
as it did not concentrate on the extreme points of the projection,
its worst-case time is much higher (by an exponential factor) than
the algorithm presented here.  Given a generalized incidence graph
[2] of a polyhedron P and a point p (or a direction d), the
generalized incidence graph of the a new polyhedron (one that include
p or d), can be built using the extended beneath beyond algorithm
given in [2].  The use of the extended beneath beyond method, insures
the reduction of the generated set of constraints for Q[x].  A
different approach (which avoids the building of the generalized
incidence graph) is presented in [5], at the cost of more checking
and generating redundancy.

      The following section describes the procedure projection.  The
procedure uses the descriptions of Q and X and builds the generalized
incidence graph of Q[x]  (all are global data structure).  The
algorithm depends on the ability to bound the polyhedron, solve the
bounded case and extend the solution to that of the unbounded case.

      Outline of the five procedures used...