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

Subject: Re: [Boost-users] Intersection Points in Higher Dimension
From: Chaman Singh Verma (csv610_at_[hidden])
Date: 2008-11-28 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 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<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?
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users

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