Lakshminarayanan Renganarayana wrote:
I am interested in knowing the time/space complexity of computing the bounding box of a polyhedra given in constraint form.
By looking at the manuals, I found that PPL supports such a computation. However, I am not able to find out its complexity.
Dear Lakshminarayanan,
have you looked at the documentation of method Polyhedron::shrink_bounding_box() and class Complexity_Class? They are here
http://www.cs.unipr.it/ppl/Documentation/user/classParma__Polyhedra__Library...
and here
http://www.cs.unipr.it/ppl/Documentation/user/group__PPL__CXX__interface.htm...
To that information I can add that POLYNOMIAL_COMPLEXITY will give a possibly approximated result. Both SIMPLEX_COMPLEXITY and ANY_COMPLEXITY will instead give an exact result. The cost of the latter is exponential both in time and space. Please let us know if this answers your question. All the best,
Roberto