Thursday, November 29, 2012
10:00 AM - 11:00 AM
Technological Institute, L324
2145 Sheridan Road
Evanston, IL 60208 map it
Audience: Faculty/Staff - Student - Public
Category: Lectures & Meetings
The EECS Department welcomes Prof. Timothy Chan of the University of Waterloo.
Prof. Chan will speak on Thursday November 29 in Room L324 of the Technological Institute. His talk is titled "Transdichotomous Geometric Algorithms, or How to Beat O(n log n) in Computational Geometry".
Many standard problems in computational geometry---for example, constructing the convex hull of n points in 3D, detecting intersections among n line segments in 2D, and performing n nearest neighbor searches among n points in 2D---are known to have efficient O(n log n)-time algorithms. These algorithms are worst-case optimal in comparison-based computational models. Recently, it has been shown that surprisingly all these problems can, in theory, be solved in time better than O(n log n) in a reasonable "transdichotomous" or "word RAM" model. The key lies in the design of new sublogarithmic data structures for a 2D "point location" problem. This talk will survey the best current results on orthogonal and general point location.
Please click the "More Info" link above to read the full abstract and Prof. Chan's bio.