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.