Re: [Boost-users] Intersection Points in Higher Dimension

Subject: Re: [Boost-users] Intersection Points in Higher Dimension
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2008-11-28 13:04:36

Chaman Singh Verma wrote:
> How can I know the intersection points of the polytope defined by
>
>    a_1 x_1 + a_2 x_2 + ........................................  a_n
x_n = b_1
>    .
>    .
>    .

I don't see any inequality constraints, so the intersection of these
hyperplanes will just be a linear space of dimension n-m (assuming you
have m equation). So I guess you wanted to write

   a_1 x_1 + a_2 x_2 + ........................................  a_n x_n
<= b_1
   .
   .
   .

> where n is very large number. Besides knowing the corner vertices of
> the polytope, I am interested in knowing the (n-2), (n-1) simplices.

Do you really want to explicitly have the corner vertices? If I take the
n-dim unit-hypercube, it will be described by 2n inequalities, but will
have 2^n corner vertices. Therefore I doubt that it will be a good idea
to compute them explicitly.

The (n-2), (n-1) simplices are a different story, because there are
sufficient few of them that it makes sense to compute them explicitly. A
nice representation of a (n-k) simplice  would be to say which k
inequalities should be turned into equalities, and which of the other
inequalities are still significant.

> Please let me know if they can be done using CGAL.

The problem seem to be the same as determining whether a polytope given
by inequalities is non-empty, and deciding which inequalities can be
dropped without changing the polytope. "Any" solver for "linear
programming" problems can be used to do this.
I just skimmed through the CGAL docs, and they have a "linear
programming solver" in CGAL
(http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/QP_solver/Chapter_m
ain.html). I have no idea how easy to use or efficient this solver is,
but if you are already using CGAL, why not try using its linear
programming solver?