Publication at Faculty of Mathematics and Physics |
2007
Abstract
(This is an extenced 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.