Efficient edge-skeleton computation for polytopes defined by oracles

DOI10.1016/j.jsc.2015.06.001zbMath1336.68262arXiv1412.3987OpenAlexW1837134879WikidataQ57908652 ScholiaQ57908652MaRDI QIDQ491253

Ioannis Z. Emiris, Bernd Gärtner, Vissarion Fisikopoulos

Publication date: 24 August 2015

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.3987

zbMATH Keywords

linear optimizationedge-skeletongeneral dimensionpolytope oracletotal polynomial-timevertex enumeration

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Pruning Algorithms for Pretropisms of Newton Polytopes

Uses Software

• iB4e
• TOPCOM
• triangulation
• respol

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constructions and complexity of secondary polytopes
• Edge-directions of standard polyhedra with applications to network flows
• Matroid polytopes and their volumes
• Triangulations. Structures for algorithms and applications
• Convex integer maximization via Graver bases
• Brick decompositions and the matching rank of graphs
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
• Geometric algorithms and combinatorial optimization.
• On the Newton polytope of the resultant
• How good are convex hull algorithms?
• On the \(k\)-systems of a simple polytope
• Computing mixed volume and all mixed cells in quermassintegral time
• Convex combinatorial optimization
• Decomposing the secondary Cayley polytope
• The use of edge-directions and linear programming to enumerate vertices
• From the zonotope construction to the Minkowski addition of convex polytopes
• AN ORACLE-BASED, OUTPUT-SENSITIVE ALGORITHM FOR PROJECTIONS OF RESULTANT POLYTOPES
• Lectures on Polytopes
• A New Approach to the Analysis of Free Rotations of Rigid Bodies
• The volume of the Newton polytope of a discriminant
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension
• The maximum numbers of faces of a convex polytope
• iB4e: A Software Framework for Parametrizing Specialized LP Problems