
Boost Users : 
Subject: Re: [Boostusers] Intersection Points in Higher Dimension
From: Chaman Singh Verma (csv610_at_[hidden])
Date: 20081128 13:41:55
On Fri, Nov 28, 2008 at 11:34 PM, Thomas Klimpel <
Thomas.Klimpel_at_[hidden]> wrote:
> 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<http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/QP_solver/Chapter_main.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 mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
Hello,
Although I am not 100% sure, but I think I will need corner vertices of the
polytopes to make Polytope round ( as suggested some of the papers to
calculate the volume) around small dihedral angles.
I will work on the solution from the hints you have given.
Thanks a lot.
csv
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