The lexico-smallest representation of convex polyhedra

Every convex polyhedron in the Euclidean space $R^d$ admits both H- and V-representation. For both formats, a representation is canonical if it is minimal and unique up to some elementary operations. In this paper, we extend the usual definition of canonical representation to a family of such representations that can be computed in polynomial time. In particular, this allows to define the lexico-smallest representation which computation is easy in practice. Furthermore, it guarantees certain sparsity property reflecting the real dimension of the studied object. As a consequence, H-representations of non-full dimensional polyhedra and V-representations of polyhedra without extreme points can be compared more efficiently.


    RO 2003 09 26


    • ROSO-REPORT-2003-005

    Record created on 2006-02-13, modified on 2016-08-08


  • There is no available fulltext. Please contact the lab or the authors.

Related material