A modification of Graham's algorithm for determining the convex hull of a finite planar set.
A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra.
Computing parametric rational generating functions with a primal Barvinok algorithm.
Configuration spaces and limits of voronoi diagrams
The Voronoi diagram of n distinct generating points divides the plane into cells, each of which consists of points most close to one particular generator. After introducing 'limit Voronoi diagrams' by analyzing diagrams of moving and coinciding points, we define compactifications of the configuration space of n distinct, labeled points. On elements of these compactifications we define Voronoi diagrams.
Constructive approximation of a ball by polytopes
Convex Polyhedra With Triangular Faces and Cone Triangulation
Cutting Hyperplanes for Divide-and-Conquer.
Decomposability of Abstract and Path-Induced Convexities in Hypergraphs
An abstract convexity space on a connected hypergraph H with vertex set V (H) is a family C of subsets of V (H) (to be called the convex sets of H) such that: (i) C contains the empty set and V (H), (ii) C is closed under intersection, and (iii) every set in C is connected in H. A convex set X of H is a minimal vertex convex separator of H if there exist two vertices of H that are separated by X and are not separated by any convex set that is a proper subset of X. A nonempty subset X of V (H) is...
Geometric algorithms and combinatorial optimization [Book]
Geometric algorithms and combinatorial optimization [Book]
Goffin's algorithm for zonotopes
The Löwner-John ellipse of a full-dimensional bounded convex set is a circumscribed ellipse with the property that if we shrink it by the factor (where is dimension), we obtain an inscribed ellipse. Goffin’s algorithm constructs, in polynomial time, a tight approximation of the Löwner-John ellipse of a polyhedron given by facet description. In this text we adapt the algorithm for zonotopes given by generator descriptions. We show that the adapted version works in time polynomial in the size...
Halving point sets.
Hardness of embedding simplicial complexes in
Let be the following algorithmic problem: Given a finite simplicial complex of dimension at most , does there exist a (piecewise linear) embedding of into ? Known results easily imply polynomiality of (; the case is graph planarity) and of for all . We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that and are undecidable for each . Our main result is NP-hardness of and, more generally, of for all , with...
L. V. Kantorovich and cutting-packing problems: new approaches for solving combinatorial problems of linear cutting and rectangular packing.
Largest j-Simplices in n-Polytopes.
Neighborly Maps with Few Vertices.
On Convex Body Chasing.
On the Difficulty of Triangulating Three-Dimensional Nonconvex Polyhedra.
On the Expected Number of k-Sets.
On the monotone upper bound problem.