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.


Year:
2003
Note:
RO 2003 09 26
Laboratories:




 Record created 2006-02-13, last modified 2018-01-27


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)