Home |
Personal Info |
Papers |
Teaching |
Interests |
People |
Links |
About |
Exact Join Detection for Convex Polyhedra and Other Numerical Abstractions (TR)
Roberto Bagnara
Dipartimento di Matematica
Università di Parma
Viale G. P. Usberti 53/A
I-43100 Parma
Italy
Patricia M. Hill
Dipartimento di Matematica
Università di Parma
Viale G. P. Usberti 53/A
I-43100 Parma
Italy
Enea Zaffanella
Dipartimento di Matematica
Università di Parma
Viale G. P. Usberti 53/A
I-43100 Parma
Italy
Abstract
Deciding whether the union of two convex polyhedra is a convex polyhedron is a basic problem in polyhedral computation having important applications in the field of constrained control and in the synthesis, analysis, verification and optimization of hardware and software systems. In these application fields, though, general convex polyhedra are only one among many so-called numerical abstractions: these range from restricted families of (not necessarily closed) convex polyhedra to non-convex geometrical objects. We thus tackle the problem from an abstract point of view: for a wide range of numerical abstractions that can be modeled as bounded join-semilattices —that is, partial orders where any finite set of elements has a least upper bound—, we show necessary and sufficient conditions for the equivalence between the lattice-theoretic join and the set-theoretic union. For the case of closed convex polyhedra —which, as far as we know, is the only one already studied in the literature— we improve upon the state-of-the-art by providing a new algorithm with a better worst-case complexity. The results and algorithms presented for the other numerical abstractions are new to this paper. All the algorithms have been implemented, experimentally validated, and made available in the Parma Polyhedra Library.
Available: PDF, 300 DPI, 600 DPI, and 1200 DPI PostScript, DVI, BibTeX entry.
[Page last updated on January 10, 2010, 18:36:41.]
bagnara@cs.unipr.it
Home | Personal | Papers | Teaching | Interests | People | Links | About