Abstract :
[en] In this thesis, we introduce three original data structures, the Convex Polyhedron Decision Diagram (CPDD), the Decomposed Convex Polyhedron (DCP), and the Internally Decomposed Convex Polyhedron (IDCP), suited for representing symbolically convex polyhedra in high-dimensional spaces. For each of them, we develop an extensive set of algorithms for constructing elementary sets, manipulating them with operators such as intersection, affine transformation, Cartesian product, and Minkowski sum, and performing other specialized operations such as computing the convex hull of two sets, and enumerating the geometrical components of a polyhedron. Each such algorithm is described in pseudocode, and its principles of operation are illustrated with concrete examples.
Our three data structures combine features of the double-description method and automata-based representations. In particular, they are easily reducible into a canonical form, which eases comparison operations between represented polyhedra. The CPDD essentially consists in an explicit description of the face lattice of a polyhedron, enhanced with algebraic structures. This approach presents a significant advantage over the double-description method, leading in particular to a more efficient implementation of the projection operation. The main drawback of this solution is that it suffers from combinatorial explosion when handling polyhedra in high-dimensional spaces, e.g., the representation of an $n$-cube takes $O(2^n)$ space. With the DCP data structure, we introduce a novel decomposition mechanism that represents some polyhedra as combinations of simpler sets. This leads to concise representations that are able to overcome combinatorial explosion in a broad range of situations. The IDCP representation further generalizes the DCP by extending the way it exploits the decomposition mechanism, obtaining an even more efficient data structure.
