Some Algorithmic Problems in Polytope Theory

2002/02/20 by Volker Kaibel, Kaibel, Volker, Marc E. Pfetsch +1 · 2 citations
Computer Science · Engineering · Mathematics · #52Bxx (Primary) 68Q25 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #graph theory and CDMA systems #math.CO #math.MG #msc:52Bxx #msc:68Q25

paper · pdf · doi:10.48550/arxiv.math/0202204

arxiv created 2002/02/20 · openalex publication_date 2002/02/20 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This is a survey on algorithmic questions about combinatorial and geometric properties of convex polytopes. We give a list of 35 problems; for each the current state of knowledege on its theoretical complexity status is reported. The problems are grouped into the sections ``Coordinate Descriptions'', ``Combinatorial Structure'', ``Isomorphism'', ``Optimization'', ``Realizability'', and ``Beyond Polytopes''.

Cited by

• Short circuit walks in fixed dimension
• Extendability of 1-decomposable complexes

Related

• Problems on Polytopes, Their Groups, and Realizations
• On the Complexity of Polytope Isomorphism Problems
• Notes on Convex Sets, Polytopes, Polyhedra, Combinatorial Topology, Voronoi Diagrams and Delaunay Triangulations
• Lectures on 0/1-polytopes
• Geometric Combinatorics of Transportation Polytopes and the Behavior of the Simplex Method