Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
From MaRDI portal
Publication:2391831
DOI10.1007/s00454-013-9503-3zbMath1279.52022OpenAlexW1978748826MaRDI QIDQ2391831
Maarten Löffler, David Eppstein
Publication date: 5 August 2013
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-013-9503-3
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial complexity of geometric structures (52C45)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new polynomial-time algorithm for linear programming
- Manhattan orbifolds
- Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
- Voronoi diagrams from convex hulls
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- Polytope pairs and their relationship to linear programming
- An optimal convex hull algorithm in any fixed dimension
- How good are convex hull algorithms?
- A complexity bound on faces of the hull complex
- Structure of a simple scheduling polyhedron
- Voronoi drawings of trees
- Tropical convexity
- The upper bound theorem for polytopes: An easy proof of its asymptotic version
- A subexponential bound for linear programming
- Computing the bounded subcomplex of an unbounded polyhedron
- Dimensions of tight spans
- Characterization of the distance between subtrees of a tree by the associated tight span
- Six theorems about injective metric spaces
- The Complexity of Vertex Enumeration Methods
- Towards a Genuinely Polynomial Algorithm for Linear Programming
- Smoothed analysis of algorithms
- Trees with Convex Faces and Optimal Angles
- Finding the convex hull facet by facet
- A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets
- Finding the k Shortest Paths
- Generosity Helps or an 11-Competitive Algorithm for Three Servers
- Lectures on Polytopes
- The quickhull algorithm for convex hulls
- Convex Polytopes
- An Algorithm for Convex Polytopes
- The maximum numbers of faces of a convex polytope
- Interior Point Methods for Linear Optimization
- Optimality and Degeneracy in Linear Programming
