Department of
Applied
Mathematics

Removing degeneracy may require unbounded dimension increase

Petr Skovron

KAM, MFF UK

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.

Our result 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. We prove that in order to remove degeneracies of an LP-type problem, we sometimes have to increase its combinatorial dimension by an arbitrarily large amount.