[PPL-devel] Complexity of bounding box computation

[Roberto Bagnara]

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#a8e306e644338f6c542b41788deb9013

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 at cs.unipr.it