Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 29, 2007, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Jack Snoeyink (Univ. of North Carolina at Chapel Hill)
1. How much time does it take to compute the diameter or convex hull of the intersection points of a set of n lines (the finite vertices of their arrangement)?
2. What if you are given n line segments?
3. What if you are given n planes?
Over 20 years ago, Ching and Lee (and Atallah) answered the first question: Theta(n log n) time, even though the arrangement can have Theta(n^2) intersections -- the extreme points must be intersections of lines that are consecutive in slope order. This observation does not help us for questions #2 or #3, however. I'll present the answers in today's seminar.
This result has no known practical application, other than to partially refute Emo's accusation that I do applied work.
Joint work with Esther Arkin and Joseph Mitchell.
Automatic MiSe System Software Version 1.4803M | admin login