Algorithms for the frame of a finitely generated unbounded polyhedron

Algorithms for the frame of a finitely generated unbounded polyhedron

0.00 Avg rating0 Votes
Article ID: iaor2007419
Country: United States
Volume: 18
Issue: 1
Start Page Number: 97
End Page Number: 110
Publication Date: Dec 2006
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: geometry
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.

Reviews

Required fields are marked *. Your email address will not be published.