On canonical representations of convex polyhedra

By K. Fukuda, S. Picozzi, D. Avis. 2002

50 citations recorded by the source corpus.

Every convex polyhedron in the Euclidean space $R^d$ admits both H-representation and V-representation. When working with convex polyhedra, in particular large-scale ones in high dimensions, it is useful to have a canonical representation that is minimal and unique up to some elementary operations. Such a representation allows one to compare two H-polyhedra or two V-polyhedra efficiently. In this paper, we define such representations that are simple and can be computed in polynomial time. The key ingredients are redundancy removal for linear inequality systems and affine transformations of polyhedra.

Subfields: Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/400a2dc73c8b96bebeaac8264a3978b25489bb4e