On Thu, 04 Oct 2007 11:37:44 +0200 Roberto Bagnara bagnara@cs.unipr.it wrote:
I would like to know the complexity of some operations in PPL : intersection, union, and difference of 2 sets, and the emptiness test of a set. Could you please give me a rough algorithmical complexity, or a reference to a paper/presentation detailing them ?
We have just added a FAQ page to the PPL web site. Please check if this answers your question. If not, please do not hesitate to come back to us (this time we will answer very quickly :-)
Hello Roberto,
I'm also interested getting some references regarding the complexity of polyhedral computations. I've read the FAQ, but I wonder if you can provide a more precise answer or perhaps some references.
Quotting the FAQ: "Most important operations on these abstractions use exponential time and space in the worst case."
But is this exponential in the number of constraints or dimensions? My experience is that increasing the dimensions has a much higher impact on the running time.
BTW, I am only interested in the closed convex polyhedra, particularly the hulling and widening operations.
Best regards,
Pedro