Timothy Chan


Research Interests

Professor Chan's research interests are in algorithms and data structures, particularly in the area of computational geometry.

He has made contributions to many fundamental problems in computational geometry, such as convex hulls, Voronoi diagrams, line segment intersection, low-dimensional linear programming, point location, and range searching. More recent directions of research include approximation algorithms for geometric optimization problems (e.g., finding independent sets in intersection graphs), geometric algorithms for massive data sets under different streaming models, and geometric data structures in the Word RAM model (e.g., generalizing "fusion trees" and "van Emde Boas trees" to higher dimensions).

Besides geometry, he has worked on a few well-known algorithmic problems such as all-pairs shortest paths and dynamic graph connectivity. He is also interested in purely mathematical (e.g., Erdos-type) problems from combinatorial geometry.

Degrees and Awards

BA (Rice), PhD (British Columbia)

University Research Chair (2005-2011); Premier's Research Excellence Award, Government of Ontario (2000-2003)

Representative Publications

T. M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. SIAM Journal on Computing, 39(5):2075-2089, 2010.

T. M. Chan and M. Patrascu. Counting inversions, offline orthogonal range counting, and related problems. In Proc. 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 161-173, 2010.

T. M. Chan. A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. Journal of the ACM, 57(3):16, 2010.

T. M. Chan and S. Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. In Proc. 25th ACM Symposium on Computational Geometry (SoCG), pages 333-340, 2009.

P. Afshani, J. Barbay, and T. M. Chan. Instance-optimal geometric algorithms. In Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS), pages 129-138, 2009.

University of Waterloo
Contact information: