Files

Abstract

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.

Details

Actions

Preview