Computer Science – Computational Geometry
Scientific paper
2010-01-23
Computer Science
Computational Geometry
12 pages, prepared for the Proceedings of the Symposium on Theoretical Aspects of Computer Science, 2010, Nancy, France
Scientific paper
10.4230/LIPIcs.STACS.2010.2443
We develop a tropical analogue of the classical double description method allowing one to compute an internal representation (in terms of vertices) of a polyhedron defined externally (by inequalities). The heart of the tropical algorithm is a characterization of the extreme points of a polyhedron in terms of a system of constraints which define it. We show that checking the extremality of a point reduces to checking whether there is only one minimal strongly connected component in an hypergraph. The latter problem can be solved in almost linear time, which allows us to eliminate quickly redundant generators. We report extensive tests (including benchmarks from an application to static analysis) showing that the method outperforms experimentally the previous ones by orders of magnitude. The present tools also lead to worst case bounds which improve the ones provided by previous methods.
Allamigeon Xavier
Gaubert Stephane
Goubault Eric
No associations
LandOfFree
The tropical double description method does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The tropical double description method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The tropical double description method will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-514823