Algorithms for the Frame of a Finitely Generated Unbounded Polyhedron

INFORMS Journal on Computing · 2006 · Volume 18 · Issue 1

Abstract

Consider two finite sets 𝒜 and 𝒱 of points in m -dimensional space. The convex hull of 𝒜 and the conical hull of 𝒱 can be combined to create a finitely generated unbounded polyhedron . We explore the geometry of these polyhedral sets to design, implement, test, and compare two different algorithms for finding the frame , a minimal-cardinality subset of 𝒜 and 𝒱, that generates the same polyhedron. One algorithm is a naive approach based on the direct application of the definition of these sets. The second algorithm is based on different principles erecting the frame geometrically one element at a time. Testing indicates that the second algorithm is faster with the difference becoming increasingly dramatic as the cardinality of the sets 𝒜 and 𝒱 increases and frame density decreases.

Keywords

linear programming, extreme points and rays, convex analysis

Enable JavaScript for citation tools and additional paper interactions.