R. Seidel

collaborators

2 papers

cs.CG2005

Upper Bound on the Number of Vertices of Polyhedra with $0, 1$ -Constraint Matrices

Khaled Elbassioni, Zvi Lotker, Raimund Seidel

In this note we show that the maximum number of vertices in any polyhedron $P = {x \in R^{d} : A x \leq b}$ with $0, 1$ -constraint matrix $A$ and a real vector $b$ is at most $d…

math.CO2002

A better upper bound on the number of triangulations of a planar point set

Francisco Santos, Raimund Seidel

We show that a point set of cardinality $n$ in the plane cannot be the vertex set of more than $5 9^{n} O (n^{- 6})$ straight-edge triangulations of its convex hull. This improves the p…

Upper Bound on the Number of Vertices of Polyhedra with 0,1-Constraint Matrices

A better upper bound on the number of triangulations of a planar point set

Upper Bound on the Number of Vertices of Polyhedra with $0, 1$ -Constraint Matrices