|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)
Convex hulls of intersections of line segments and planes
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
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
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.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.3392 | admin login