Complexity of bounding box computation
Hi,
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.
Any ideas?
Thanks in advance for any replies.
Ln.
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
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
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.
[...]
Dear Lakshminarayanan,
[...]
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.
[...]
Roberto and Lakshminarayanan,
actually the implementation for the case SIMPLEX_COMPLEXITY will return an approximate answer, since it is not complete yet. The fact is that this programming task was marked as a low priority one due to a number of reasons ... as things are now, there is nothing (except time constraints, of course) preventing us from providing an exact implementation of the method using the simplex for C_Polyhedron. We may still resort to approximation in the case of NNC_Polyhedron, as our simplex does not handles strict constraints.
Ciao, Enea.
participants (3)
-
Enea Zaffanella -
Lakshminarayanan Renganarayana -
Roberto Bagnara