Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 23, 2021, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Saeed Ilchi
Consider a perfect matching M on a point set of size 2n in the plane. A point p is a k-detour for M if for any matched pair of points (a,b), we have |a - p| + |p - b| ≤ k|a - b|. For any point set, we show that there is always a matching with a 2/sqrt(3)-detour. This is tight due to a simple lower bound that can be obtained from equilateral triangles. The best previous bound was sqrt(2).
This is a joint work with Bernd Gärtner, Yoshio Okamoto, Patrick Schnider, and Tim Taubner.
Automatic MiSe System Software Version 1.4803M | admin login