Theory of Computing
-------------------
Title : Removing Degeneracy May Require a Large Dimension Increase
Authors : Jiri Matousek and Petr Skovron
Volume : 3
Number : 8
Pages : 159-177
URL : https://theoryofcomputing.org/articles/v003a008
Abstract
--------
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.