Convex hulls, oracles, and homology

DOI10.1016/j.jsc.2003.08.006zbMath1121.52030arXivmath/0301100OpenAlexW2066473765WikidataQ117245108 ScholiaQ117245108MaRDI QIDQ2643561

Michael Joswig, Günter M. Ziegler

Publication date: 24 August 2007

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

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

zbMATH Keywords

convex hull algorithmsimplicial homology computation

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Computing convex hulls and counting integer points with \texttt{polymake}, Which nonnegative matrices are slack matrices?, A new algorithm for computing the convex hull of a planar point set, A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations, An efficient local approach to convexity testing of piecewise-linear hypersurfaces, Sum of Squares Certificates for Containment of $\mathcal{H}$-Polytopes in $\mathcal{V}$-Polytopes

Uses Software

• cdd
• polymake

Cites Work

• Small-dimensional linear programming and convex hulls made easy
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Primal-dual methods for vertex and facet enumeration
• Incremental convex hull algorithms are not output sensitive
• Geometric algorithms and combinatorial optimization.
• An optimal convex hull algorithm in any fixed dimension
• How good are convex hull algorithms?
• Birkhoff's theorem and convex hulls of Coxeter groups
• Vertex-facet incidences of unbounded polyhedra
• On the complexity of four polyhedral set containment problems
• Lectures on Polytopes
• Polymake: an approach to modular software design in computational geometry
• The maximum numbers of faces of a convex polytope
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item