Removing degeneracy may require a large dimension increase

Abstract

The result can be regarded as an indication that the problem of removing degeneracies in geometric computations 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.

Keywords

• Removing
• degeneracy
• require
• large
• dimension
• increase