Timothy M. Chan
Orcid: 0000-0002-8093-0675Affiliations:
- University of Illinois, Urbana, IL, USA
- University of Waterloo, Canada (former)
According to our database1,
Timothy M. Chan
authored at least 213 papers
between 1994 and 2024.
Collaborative distances:
Collaborative distances:
Awards
ACM Fellow
ACM Fellow 2019, "For contributions to computational geometry, algorithms, and data structures".
Timeline
Legend:
Book In proceedings Article PhD thesis Dataset OtherLinks
Online presence:
-
on zbmath.org
-
on orcid.org
On csauthors.net:
Bibliography
2024
Hopcroft's Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision Trees.
ACM Trans. Algorithms, July, 2024
Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching.
CoRR, 2024
Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024
An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
Proceedings of the 40th International Symposium on Computational Geometry, 2024
Proceedings of the 40th International Symposium on Computational Geometry, 2024
Proceedings of the 40th International Symposium on Computational Geometry, 2024
Proceedings of the 40th International Symposium on Computational Geometry, 2024
2023
Discret. Comput. Geom., September, 2023
Minimum L<sub>∞</sub> Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem.
CoRR, 2023
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023
Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size.
Proceedings of the 39th International Symposium on Computational Geometry, 2023
Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem.
Proceedings of the 39th International Symposium on Computational Geometry, 2023
2022
J. Comput. Geom., 2022
Corrigendum to "Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points" [Comput. Geom. 60 (2017) 2-7].
Comput. Geom., 2022
Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022
2021
Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky.
ACM Trans. Algorithms, 2021
Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
(Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021
Proceedings of the 29th Annual European Symposium on Algorithms, 2021
All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error.
Proceedings of the 29th Annual European Symposium on Algorithms, 2021
Proceedings of the 37th International Symposium on Computational Geometry, 2021
2020
More Logarithmic-factor Speedups for 3SUM, (median, +)-convolution, and Some Geometric 3SUM-hard Problems.
ACM Trans. Algorithms, 2020
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020
Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020
Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020
Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020
Proceedings of the Graph Drawing and Network Visualization - 28th International Symposium, 2020
Proceedings of the 36th International Symposium on Computational Geometry, 2020
Proceedings of the 36th International Symposium on Computational Geometry, 2020
2019
J. Comput. Geom., 2019
Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back.
Discret. Comput. Geom., 2019
Algorithmica, 2019
Algorithmica, 2019
Guarding Orthogonal Art Galleries with Sliding k-Transmitters: Hardness and Approximation.
Algorithmica, 2019
Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019
2018
ACM Trans. Algorithms, 2018
J. Comput. Geom., 2018
Inf. Process. Lett., 2018
Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018
Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity.
Proceedings of the 29th International Symposium on Algorithms and Computation, 2018
Proceedings of the 34th International Symposium on Computational Geometry, 2018
2017
Comput. Geom., 2017
Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points.
Comput. Geom., 2017
Proceedings of the WALCOM: Algorithms and Computation, 2017
Proceedings of the Graph Drawing and Network Visualization - 25th International Symposium, 2017
2016
Discret. Comput. Geom., 2016
A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions.
Discret. Comput. Geom., 2016
Proceedings of the 27th International Symposium on Algorithms and Computation, 2016
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016
Proceedings of the 32nd International Symposium on Computational Geometry, 2016
Proceedings of the 32nd International Symposium on Computational Geometry, 2016
2015
J. Graph Algorithms Appl., 2015
Discret. Comput. Geom., 2015
Comput. Geom., 2015
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
Proceedings of the Algorithms and Computation - 26th International Symposium, 2015
Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015
Proceedings of the 27th Canadian Conference on Computational Geometry, 2015
2014
Theory Comput. Syst., 2014
Inf. Process. Lett., 2014
Comput. Geom., 2014
Exact algorithms and APX-hardness results for geometric packing and covering problems.
Comput. Geom., 2014
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014
Proceedings of the Algorithms - ESA 2014, 2014
Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014
Proceedings of the 26th Canadian Conference on Computational Geometry, 2014
2013
ACM Trans. Algorithms, 2013
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013
Proceedings of the Algorithms and Computation - 24th International Symposium, 2013
Proceedings of the Graph Drawing - 21st International Symposium, 2013
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013
Proceedings of the Space-Efficient Data Structures, 2013
2012
All-pairs shortest paths for unweighted undirected graphs in <i>o</i>(<i>mn</i>) time.
ACM Trans. Algorithms, 2012
Discret. Comput. Geom., 2012
Discret. Comput. Geom., 2012
Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012
Proceedings of the Ninth International Symposium on Voronoi Diagrams in Science and Engineering, 2012
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012
Proceedings of the Graph Drawing - 20th International Symposium, 2012
Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set.
Proceedings of the 28th ACM Symposium on Computational Geometry, 2012
2011
Computational Geometry for Non-Geometers: Recent Developments on Some Classical Problems.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011
2010
SIAM J. Comput., 2010
J. ACM, 2010
Optimal in-place and cache-oblivious algorithms for 3-d convex hulls and 2-d segment intersection.
Comput. Geom., 2010
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010
2009
Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time.
SIAM J. Comput., 2009
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009
2008
All-Pairs Shortest Paths with Real Weights in <i>O</i> ( <i>n</i> <sup>3</sup>/log <i>n</i> ) Time.
Algorithmica, 2008
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008
2007
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007
2006
Int. J. Comput. Geom. Appl., 2006
Comput. Geom., 2006
Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time.
Comput. Geom., 2006
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006
Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006
Proceedings of the Algorithms, 2006
Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006
2005
Discret. Comput. Geom., 2005
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005
2004
Inf. Process. Lett., 2004
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004
Space-E.cient Algorithms for Computing the Convex Hull of a Simple Polygonal Line in Linear Time.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004
2003
J. Algorithms, 2003
Proceedings of the 19th ACM Symposium on Computational Geometry, 2003
Proceedings of the 15th Canadian Conference on Computational Geometry, 2003
Proceedings of the 15th Canadian Conference on Computational Geometry, 2003
2002
Approximating the Diameter, Width, Smallest Enclosing Cylinder, and Minimum-Width Annulus.
Int. J. Comput. Geom. Appl., 2002
Comput. Geom., 2002
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002
Proceedings of the 14th Canadian Conference on Computational Geometry, 2002
Proceedings of the 14th Canadian Conference on Computational Geometry, 2002
2001
J. ACM, 2001
Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001
2000
Random Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions.
SIAM J. Comput., 2000
Comput. Geom., 2000
1999
Discret. Comput. Geom., 1999
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
1998
Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming.
J. Algorithms, 1998
Inf. Process. Lett., 1998
Discret. Comput. Geom., 1998
Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998
1997
Primal Dividing and Dual Pruning: Output-Sensitive Construction of Four-Dimensional Polytopes and Three-Dimensional Voronoi Diagrams.
Discret. Comput. Geom., 1997
1996
Discret. Comput. Geom., 1996
Discret. Comput. Geom., 1996
Proceedings of the Graph Drawing, Symposium on Graph Drawing, 1996
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996
1995
Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995
Proceedings of the 7th Canadian Conference on Computational Geometry, 1995
1994
A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections.
Proceedings of the 6th Canadian Conference on Computational Geometry, 1994