Volume 3 (2007) Article 8 pp. 159-177

Removing Degeneracy May Require a Large Dimension Increase

by Jiří Matoušek and Petr Škovroň

Received: March 12, 2007
Published: September 26, 2007
DOI: 10.4086/toc.2007.v003a008

Download article from ToC site:
[PS (519K)]    [PS.GZ (156K)]    [PS.ZIP (156K)]
[PDF (228K)]    [DVI (142K)]    [ZIP (99K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: LP-type problem, degeneracy, general position, geometric computation, partially ordered set
Categories: algorithms, geometric algorithms, lower bounds
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+ε)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.