Efficient edge-skeleton computation for polytopes defined by oracles

DOI10.1016/J.JSC.2015.06.001MaRDI QIDQ491253zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ioannis Z. Emiris, B. 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) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)

Abstract: In general dimension, there is no known total polynomial algorithm for either convex hull or vertex enumeration, i.e. an algorithm whose complexity depends polynomially on the input and output sizes. It is thus important to identify problems (and polytope representations) for which total polynomial-time algorithms can be obtained. We offer the first total polynomial-time algorithm for computing the edge-skeleton (including vertex enumeration) of a polytope given by an optimization or separation oracle, where we are also given a superset of its edge directions. We also offer a space-efficient variant of our algorithm by employing reverse search. All complexity bounds refer to the (oracle) Turing machine model. There is a number of polytope classes naturally defined by oracles; for some of them neither vertex nor facet representation is obvious. We consider two main applications, where we obtain (weakly) total polynomial-time algorithms: Signed Minkowski sums of convex polytopes, where polytopes can be subtracted provided the signed sum is a convex polytope, and computation of secondary, resultant, and discriminant polytopes. Further applications include convex combinatorial optimization and convex integer programming, where we offer a new approach, thus removing the complexity's exponential dependence in the dimension.

Recommendations

• Oracle-polynomial-time approximation of largest simplices in convex bodies
• An exact algorithm for constructing minimum Euclidean skeletons of polygons
• Optimal computation of finitely oriented convex hulls
• An oracle-based, output-sensitive algorithm for projections of resultant polytopes
• Computing convex-straight-skeleton Voronoi diagrams for segments and convex polygons
• A fast and efficient algorithm for determining the connected orthogonal convex hulls
• Computing skeletons for rectilinearly convex obstacles in the rectilinear plane
• Fast edge-searching and related problems
• Fast algorithms for computing \(\beta\)-skeletons and their relatives.
• Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon

Cites work

• scientific article; zbMATH DE number 3637614 (Why is no real title available?)
• scientific article; zbMATH DE number 575960 (Why is no real title available?)
• scientific article; zbMATH DE number 1961536 (Why is no real title available?)
• scientific article; zbMATH DE number 236540 (Why is no real title available?)
• A New Approach to the Analysis of Free Rotations of Rigid Bodies
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• An oracle-based, output-sensitive algorithm for projections of resultant polytopes
• Brick decompositions and the matching rank of graphs
• Computing mixed volume and all mixed cells in quermassintegral time
• Constructions and complexity of secondary polytopes
• Convex combinatorial optimization
• Convex integer maximization via Graver bases
• Decomposing the secondary Cayley polytope
• Edge-directions of standard polyhedra with applications to network flows
• From the zonotope construction to the Minkowski addition of convex polytopes
• Geometric algorithms and combinatorial optimization.
• How good are convex hull algorithms?
• Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension
• Lectures on Polytopes
• Matroid polytopes and their volumes
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• On the Newton polytope of the resultant
• On the \(k\)-systems of a simple polytope
• The maximum numbers of faces of a convex polytope
• The use of edge-directions and linear programming to enumerate vertices
• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
• The volume of the Newton polytope of a discriminant
• Triangulations. Structures for algorithms and applications
• iB4e: a software framework for parametrizing specialized LP problems

Cited in

(1)

• Pruning algorithms for pretropisms of Newton polytopes

Describes a project that uses

Uses Software

• iB4e
• TOPCOM
• triangulation
• respol

This page was built for publication: Efficient edge-skeleton computation for polytopes defined by oracles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491253)