Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 23, 2012, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Sonoko Moriyama (Tohoku University)
The smallest enclosing ball problem (for short, the SEB problem) is known as one of classical problems of computational geometry. Given a set of n points in a d dimensional space, this problem is to find the d dimensional ball with the smallest radius which encloses all the n points of P. Szabo and Welzl in 2001 showed that if all the n points are affinely independent, the SEB problem is formulated as finding a unique sink on a unique sink orientation on an n-dimensional cube, called an SEB cube. There is another combinatorial condition defined on a unique sink orientation, Holt-Klee condition proposed by Holt and Klee in 1999. The Holt-Klee condition represents a directed version of the n-connectivity property of a unique sink orientation. In this talk, we prove that every SEB cube satisfies the Holt-Klee condition.
Automatic MiSe System Software Version 1.4803M | admin login