
Boost Users : 
Subject: Re: [Boostusers] Intersection Points in Higher Dimension
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 20081128 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 nm (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 (n2), (n1) simplices.
Do you really want to explicitly have the corner vertices? If I take the
ndim unithypercube, 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 (n2), (n1) 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 (nk) 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 nonempty, 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?
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net