[PPL-devel] Complexity of bounding box computation

[Lakshminarayanan Renganarayana]

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