Timothy M. Chan

ORCID

Publication Activity (10 Years)

Years Active: 1994-2024
Publications (10 Years): 139

Top Venues

CoRR

SoCG

SODA

Discret. Comput. Geom.

Publications

Timothy M. Chan, Isaac M. Hair
Convex Polygon Containment: Improving Quadratic to Near Linear Time. SoCG (2024)
Timothy M. Chan, Zhengcheng Huang
Dynamic Geometric Connectivity in the Plane with Constant Query Time. SoCG (2024)
Timothy M. Chan, Qizheng He, Jie Xue
Enclosing Points with Geometric Objects. CoRR (2024)
Timothy M. Chan, Qizheng He, Jie Xue
Enclosing Points with Geometric Objects. SoCG (2024)
Sujoy Bhore, Timothy M. Chan
Fully Dynamic Geometric Vertex Cover and Matching. CoRR (2024)
Sujoy Bhore, Timothy M. Chan
Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching. CoRR (2024)
Timothy M. Chan, Isaac M. Hair
Convex Polygon Containment: Improving Quadratic to Near Linear Time. CoRR (2024)
Timothy M. Chan, Pingan Cheng, Da Wei Zheng
Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane. CoRR (2024)
Timothy M. Chan, Pingan Cheng, Da Wei Zheng
Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane. SoCG (2024)
Timothy M. Chan, Yinzhan Xu
Simpler Reductions from Exact Triangle. SOSA (2024)
Timothy M. Chan, Zhengcheng Huang
Dynamic Geometric Connectivity in the Plane with Constant Query Time. CoRR (2024)
Timothy M. Chan, Da Wei Zheng
Hopcroft's Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision Trees. ACM Trans. Algorithms 20 (3) (2024)
Timothy M. Chan, Pingan Cheng, Da Wei Zheng
An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism. SODA (2024)
Timothy M. Chan, Pingan Cheng, Da Wei Zheng
An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism. CoRR (2023)
Timothy M. Chan
Faster Algorithms for Largest Empty Rectangles and Boxes. Discret. Comput. Geom. 70 (2) (2023)
Timothy M. Chan
Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem. SoCG (2023)
Timothy M. Chan, Zhengcheng Huang
Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size. SoCG (2023)
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More. CoRR (2023)
Timothy M. Chan, Qizheng He, Yuancheng Yu
On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k. ICALP (2023)
Timothy M. Chan, Da Wei Zheng
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures. SODA (2023)
Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, Yinzhan Xu
Faster Algorithms for Text-to-Pattern Hamming Distances. FOCS (2023)
Timothy M. Chan
Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs. SODA (2023)
Timothy M. Chan, Yinzhan Xu
Simpler Reductions from Exact Triangle. CoRR (2023)
Timothy M. Chan
Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem. CoRR (2023)
Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, Yinzhan Xu
Faster Algorithms for Text-to-Pattern Hamming Distances. CoRR (2023)
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More. STOC (2023)
Timothy M. Chan, Zhengcheng Huang
Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size. CoRR (2023)
Timothy M. Chan, Sariel Har-Peled
On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings. SODA (2023)
Timothy M. Chan, Qizheng He, Yuancheng Yu
On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k. CoRR (2023)
Timothy M. Chan, Qizheng He, Subhash Suri, Jie Xue
Dynamic Geometric Set Cover, Revisited. SODA (2022)
Timothy M. Chan, Yakov Nekrich, Saladi Rahul, Konstantinos Tsakalidis
Orthogonal point location and rectangle stabbing queries in 3-d. J. Comput. Geom. 13 (1) (2022)
Timothy M. Chan
Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs. CoRR (2022)
Sergio Cabello, Timothy M. Chan
Computing Shapley Values in the Plane. Discret. Comput. Geom. 67 (3) (2022)
Timothy M. Chan, Zahed Rahmati
Corrigendum to "Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points" [Comput. Geom. 60 (2017) 2-7]. Comput. Geom. 101 (2022)
Timothy M. Chan, Sariel Har-Peled, Mitchell Jones
Optimal Algorithms for Geometric Centers and Depth. SIAM J. Comput. 51 (3) (2022)
Timothy M. Chan, Da Wei Zheng
Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees. SODA (2022)
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV. CoRR (2022)
Timothy M. Chan, Qizheng He
More on change-making and related problems. J. Comput. Syst. Sci. 124 (2022)
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV. STOC (2022)
Timothy M. Chan, Da Wei Zheng
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures. CoRR (2022)
Timothy M. Chan, Saladi Rahul
Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points. STACS (2021)
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths. CoRR (2021)
Timothy M. Chan, Da Wei Zheng
Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees. CoRR (2021)
Timothy M. Chan
Faster Algorithms for Largest Empty Rectangles and Boxes. SoCG (2021)
Timothy M. Chan, Qizheng He
More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time. CoRR (2021)
Timothy M. Chan, Sariel Har-Peled
Smallest k-Enclosing Rectangle Revisited. Discret. Comput. Geom. 66 (2) (2021)
Timothy M. Chan
All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error. ESA (2021)
Timothy M. Chan
Faster Algorithms for Largest Empty Rectangles and Boxes. CoRR (2021)
Timothy M. Chan, Qizheng He
More on Change-Making and Related Problems. CoRR (2021)
Timothy M. Chan, Qizheng He
More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time. SoCG (2021)
Timothy M. Chan, Qizheng He, Subhash Suri, Jie Xue
Dynamic Geometric Set Cover, Revisited. CoRR (2021)
Timothy M. Chan, R. Ryan Williams
Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. ACM Trans. Algorithms 17 (1) (2021)
Timothy M. Chan
Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices. SODA (2021)
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths. ICALP (2021)
Timothy M. Chan, Zhengcheng Huang
Dynamic Colored Orthogonal Range Searching. ESA (2021)
Timothy M. Chan
(Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems. SODA (2021)
Timothy M. Chan, Qizheng He
On the Change-Making Problem. SOSA (2020)
Timothy M. Chan
Dynamic Geometric Data Structures via Shallow Cuttings. Discret. Comput. Geom. 64 (4) (2020)
Timothy M. Chan
Dynamic Generalized Closest Pair: Revisiting Eppstein's Technique. SOSA (2020)
Josh Alman, Timothy M. Chan, R. Ryan Williams
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions. SODA (2020)
Timothy M. Chan, Yakov Nekrich
Better Data Structures for Colored Orthogonal Range Reporting. SODA (2020)
Timothy M. Chan, Qizheng He
Faster Approximation Algorithms for Geometric Set Cover. CoRR (2020)
Timothy M. Chan, Qizheng He, Yakov Nekrich
Further Results on Colored Range Searching. SoCG (2020)
Timothy M. Chan, Qizheng He
Reducing 3SUM to Convolution-3SUM. SOSA (2020)
Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat
Approximating Text-to-Pattern Hamming Distances. CoRR (2020)
Timothy M. Chan
Tree Drawings Revisited. Discret. Comput. Geom. 63 (4) (2020)
Timothy M. Chan, Qizheng He, Yakov Nekrich
Further Results on Colored Range Searching. CoRR (2020)
Timothy M. Chan, Sariel Har-Peled, Mitchell Jones
On Locality-Sensitive Orderings and Their Applications. SIAM J. Comput. 49 (3) (2020)
Timothy M. Chan, Zhengcheng Huang
Improved Upper and Lower Bounds for LR Drawings of Binary Trees. Graph Drawing (2020)
Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat
Approximating text-to-pattern Hamming distances. STOC (2020)
Timothy M. Chan, Qizheng He
More on Change-Making and Related Problems. ESA (2020)
Timothy M. Chan, Qizheng He
Faster Approximation Algorithms for Geometric Set Cover. SoCG (2020)
Timothy M. Chan, Saladi Rahul, Jie Xue
Range closest-pair search in higher dimensions. Comput. Geom. 91 (2020)
Timothy M. Chan
More Logarithmic-factor Speedups for 3SUM, (median, +)-convolution, and Some Geometric 3SUM-hard Problems. ACM Trans. Algorithms 16 (1) (2020)
Sergio Cabello, Timothy M. Chan
Computing Shapley Values in the Plane. SoCG (2019)
Timothy M. Chan, Yakov Nekrich, Michiel H. M. Smid
Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles. WADS (2019)
Therese C. Biedl, Timothy M. Chan, Stephanie Lee, Saeed Mehrabi, Fabrizio Montecchiani, Hamideh Vosoughpour, Ziting Yu
Guarding Orthogonal Art Galleries with Sliding k-Transmitters: Hardness and Approximation. Algorithmica 81 (1) (2019)
Timothy M. Chan, Sariel Har-Peled
Smallest k-Enclosing Rectangle Revisited. CoRR (2019)
Timothy M. Chan, Zhengcheng Huang
Improved Upper and Lower Bounds for LR Drawings of Binary Trees. CoRR (2019)
Timothy M. Chan, Dimitrios Skrepetos
Faster Approximate Diameter and Distance Oracles in Planar Graphs. Algorithmica 81 (8) (2019)
Timothy M. Chan, Dimitrios Skrepetos
Approximate shortest paths and distance oracles in weighted unit-disk graphs. J. Comput. Geom. 10 (2) (2019)
Timothy M. Chan
Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back. Discret. Comput. Geom. 61 (4) (2019)
Timothy M. Chan, John Hershberger, Simon Pratt
Two Approaches to Building Time-Windowed Geometric Data Structures. Algorithmica 81 (9) (2019)
Timothy M. Chan, Dimitrios Skrepetos
All-Pairs Shortest Paths in Geometric Intersection Graphs. J. Comput. Geom. 10 (1) (2019)
Timothy M. Chan, Yakov Nekrich, Michiel H. M. Smid
Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles. CoRR (2019)
Timothy M. Chan, Saladi Rahul, Jie Xue
Range closest-pair search in higher dimensions. CoRR (2019)
Timothy M. Chan, Sariel Har-Peled, Mitchell Jones
On Locality-Sensitive Orderings and Their Applications. ITCS (2019)
Timothy M. Chan, Sariel Har-Peled
Smallest k-Enclosing Rectangle Revisited. SoCG (2019)
Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman, Aurélien Ooms
Subquadratic encodings for point configurations. J. Comput. Geom. 10 (2) (2019)
Timothy M. Chan
Dynamic Geometric Data Structures via Shallow Cuttings. SoCG (2019)
Timothy M. Chan, Saladi Rahul, Jie Xue
Range Closest-Pair Search in Higher Dimensions. WADS (2019)
Timothy M. Chan
Dynamic Geometric Data Structures via Shallow Cuttings. CoRR (2019)
Timothy M. Chan
Tree Drawings Revisited. CoRR (2018)
Timothy M. Chan, Konstantinos Tsakalidis
Dynamic Orthogonal Range Searching on the RAM, Revisited. J. Comput. Geom. 9 (2) (2018)
Timothy M. Chan, Yakov Nekrich, Saladi Rahul, Konstantinos Tsakalidis
Orthogonal Point Location and Rectangle Stabbing Queries in 3-d. CoRR (2018)
Zahed Rahmati, Timothy M. Chan
A Clustering-Based Approach to Kinetic Closest Pair. Algorithmica 80 (10) (2018)
Timothy M. Chan
Improved Deterministic Algorithms for Linear Programming in Low Dimensions. ACM Trans. Algorithms 14 (3) (2018)
Timothy M. Chan, Dimitrios Skrepetos
Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs. SoCG (2018)
Timothy M. Chan
More Logarithmic-Factor Speedups for 3SUM, (median, +)-Convolution, and Some Geometric 3SUM-Hard Problems. SODA (2018)
Timothy M. Chan
Tree Drawings Revisited. SoCG (2018)

Timothy M. Chan.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Timothy M. Chan