[PPL-devel] Complexity of bounding box computation

[Enea Zaffanella]

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.