Published: September 26, 2007

**Keywords:**LP-type problem, degeneracy, general position, geometric computation, partially ordered set

**ACM Classification:**F.2.2

**AMS Classification:**68U05, 06A07, 68R99

**Abstract:**
[Plain Text Version]

Many geometric algorithms are formulated for input objects in general position; sometimes this is for convenience and simplicity, and sometimes it is essential for the algorithm to work at all. For arbitrary inputs this requires removing degeneracies, which has usually been solved by relatively complicated and computationally demanding perturbation methods.

The result of this paper can be regarded as an indication
that the problem of removing degeneracies has no simple
“abstract” solution. We consider *LP-type
problems*, a successful axiomatic framework for optimization
problems capturing, e.g., linear programming and the smallest enclosing
ball of a point set. For infinitely many integers $D$ we construct
a $D$-dimensional LP-type problem such that
in order to remove degeneracies from it, we have to increase
the dimension to at least $(1+\epsilon)D$, where $\epsilon>0$
is an absolute constant.

The proof consists of showing that certain posets cannot be covered by pairwise disjoint copies of Boolean algebras under some restrictions on their placement. To this end, we prove that certain systems of linear inequalities are unsolvable, which seems to require surprisingly precise calculations.