Received: March 12, 2007
Published: September 26, 2007
DOI: 10.4086/toc.2007.v003a008
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+ε)D, where ε > 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.