Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 26, 2007, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Petr Škovroň (Charles Univ., Prague)
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.
Automatic MiSe System Software Version 1.4803M | admin login