Dear Prof. Bagnara,
Thanks for your immediate reply. Your explanation answers the question I had.
Thank you, Ln
On Jan 8, 2007, at 3:59 PM, Roberto Bagnara wrote:
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_1_1Polyhedron.html#a8e306e644338f6c542b 41788deb9013
and here
http://www.cs.unipr.it/ppl/Documentation/user/ group__PPL__CXX__interface.html#g113f1e845cba6b1c3c5705d0e14f1cc1
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-- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it