Computing the bounded subcomplex of an unbounded polyhedron

2010/06/30 by Sven Herrmann, Michael Joswig, Marc E. Pfetsch
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Bounded function #Combinatorics #Computer science #Discrete mathematics #Graph #Hasse diagram #Mathematics #Partially ordered set #Polyhedron #Simple (philosophy) #Topological and Geometric Data Analysis #Vertex (graph theory) #math.CO #msc:52B55

paper · pdf · doi:10.1016/j.comgeo.2011.11.002

published as Computational Geometry: Theory and Applications, 46 (2013), no. 5, 541-551 · 16 pages

arxiv created 2010/12/07 · openalex publication_date 2011/11/18 · arxiv updated 2014/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We study efficient combinatorial algorithms to produce the Hasse diagram of the poset of bounded faces of an unbounded polyhedron, given vertex-facet incidences. We also discuss the special case of simple polyhedra and present computational results.

Citations

• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Generating All Vertices of a Polyhedron Is Hard
• Six theorems about injective metric spaces
• Bounds on the f-Vectors of Tight Spans