Timothy M. Chan's Publications by Topics

Personal favorites

Computational geometry

• Approximation algorithms for NP-hard geometric problems
• Dynamic geometric data structures
• Word-RAM geometric algorithms and data structures
• Streaming geometric algorithms
• Output-sensitive/adaptive geometric algorithms
• Geometric algorithms with limited space
• Range searching
• Convex hulls
• Exact nearest neighbors
• Approximate nearest neighbors
• Point location
• Line segment intersection
• Geometric optimization techniques and low-dimensional linear programming
• Coresets
• Klee's measure problem
• Statistical depth
• Euclidean minimum spanning trees
• Geometric shortest paths
• Matrix searching
• Graph drawing
• Fine-grained complexity in computational geometry

Combinatorial/discrete geometry

• The k-level and k-set problem
• Miscellaneous geometry

Other algorithms, data structures, and fine-grained complexity

• All-pairs shortest paths
• 3SUM
• The polynomial method
• String algorithms and text indexing
• Sorting, selection, and other one-dimensional problems
• Dynamic subgraph connectivity
• Miscellaneous topics