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.