Northwestern University

Thu 10:00 AM

Prof. Timothy Chan, Transdichotomous Geometric Algorithms

When: Thursday, November 29, 2012
10:00 AM - 11:00 AM  

Where: Technological Institute, L324, 2145 Sheridan Road, Evanston, IL 60208 map it

Audience: Faculty/Staff - Student - Public

Contact: Lana Kiperman   847.467.0028

Group: Electrical Engineering & Computer Science

Category: Lectures & Meetings

More Info


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.

Add Event to Calendar

Add Event To My Group:

Please sign-in