Intersection Points in Higher Dimension
Hello, 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 . . . 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. Please let me know if they can be done using CGAL. Thanks, csv Poona, India
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?
On Fri, Nov 28, 2008 at 11:34 PM, Thomas Klimpel < Thomas.Klimpel@synopsys.com> 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.htmlhttp://www.cgal.org/Manual/3.3/doc_html/cgal_manual/QP_solver/Chapter_main.h...). 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@lists.boost.org 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
participants (2)
-
Chaman Singh Verma -
Thomas Klimpel