default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDTimothy M. Chan
Person information
- affiliation: University of Illinois, Urbana, IL, USA
- affiliation (former): University of Waterloo, Canada
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j109]Timothy M. Chan
, Da Wei Zheng:
Hopcroft's Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision Trees. ACM Trans. Algorithms 20(3): 24 (2024)- [c171]Timothy M. Chan, Pingan Cheng, Da Wei Zheng:
Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane. SoCG 2024: 33:1-33:15 - [c170]Timothy M. Chan, Isaac M. Hair:
Convex Polygon Containment: Improving Quadratic to Near Linear Time. SoCG 2024: 34:1-34:15 - [c169]Timothy M. Chan, Qizheng He, Jie Xue:
Enclosing Points with Geometric Objects. SoCG 2024: 35:1-35:15 - [c168]Timothy M. Chan, Zhengcheng Huang:
Dynamic Geometric Connectivity in the Plane with Constant Query Time. SoCG 2024: 36:1-36:13 - [c167]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: 4451-4463 - [c166]Timothy M. Chan, Yinzhan Xu:
Simpler Reductions from Exact Triangle. SOSA 2024: 28-38 - [e4]Timothy M. Chan, Johannes Fischer, John Iacono, Grzegorz Herman:
32nd Annual European Symposium on Algorithms, ESA 2024, September 2-4, 2024, Royal Holloway, London, United Kingdom. LIPIcs 308, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2024, ISBN 978-3-95977-338-6 [contents] - [i49]Timothy M. Chan, Zhengcheng Huang:
Dynamic Geometric Connectivity in the Plane with Constant Query Time. CoRR abs/2402.05357 (2024) - [i48]Sujoy Bhore, Timothy M. Chan:
Fully Dynamic Geometric Vertex Cover and Matching. CoRR abs/2402.07441 (2024) - [i47]Timothy M. Chan, Qizheng He, Jie Xue:
Enclosing Points with Geometric Objects. CoRR abs/2402.17322 (2024) - [i46]Timothy M. Chan, Pingan Cheng, Da Wei Zheng:
Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane. CoRR abs/2403.12303 (2024) - [i45]Timothy M. Chan, Isaac M. Hair:
Convex Polygon Containment: Improving Quadratic to Near Linear Time. CoRR abs/2403.13292 (2024) - [i44]Sujoy Bhore, Timothy M. Chan:
Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching. CoRR abs/2407.20659 (2024) - 2023
- [j108]Timothy M. Chan:
Faster Algorithms for Largest Empty Rectangles and Boxes. Discret. Comput. Geom. 70(2): 355-375 (2023) - [c165]Timothy M. Chan, Zhengcheng Huang:
Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size. SoCG 2023: 23:1-23:16 - [c164]Timothy M. Chan:
Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem. SoCG 2023: 24:1-24:13 - [c163]Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, Yinzhan Xu:
Faster Algorithms for Text-to-Pattern Hamming Distances. FOCS 2023: 2188-2203 - [c162]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: 34:1-34:19 - [c161]Timothy M. Chan, Sariel Har-Peled:
On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings. SODA 2023: 1398-1413 - [c160]Timothy M. Chan, Da Wei Zheng:
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures. SODA 2023: 1493-1511 - [c159]Timothy M. Chan:
Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs. SODA 2023: 1777-1805 - [c158]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: 419-432 - [i43]Timothy M. Chan:
Minimum L∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem. CoRR abs/2303.09122 (2023) - [i42]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 abs/2303.14572 (2023) - [i41]Timothy M. Chan, Zhengcheng Huang:
Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size. CoRR abs/2303.16303 (2023) - [i40]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 abs/2305.01892 (2023) - [i39]Timothy M. Chan, Yinzhan Xu:
Simpler Reductions from Exact Triangle. CoRR abs/2310.11575 (2023) - [i38]Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, Yinzhan Xu:
Faster Algorithms for Text-to-Pattern Hamming Distances. CoRR abs/2310.13174 (2023) - [i37]Timothy M. Chan, Pingan Cheng, Da Wei Zheng:
An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism. CoRR abs/2310.15363 (2023) - 2022
- [j107]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: 101831 (2022) - [j106]Sergio Cabello, Timothy M. Chan:
Computing Shapley Values in the Plane. Discret. Comput. Geom. 67(3): 843-881 (2022) - [j105]Timothy M. Chan, Qizheng He:
More on change-making and related problems. J. Comput. Syst. Sci. 124: 159-169 (2022) - [j104]Timothy M. Chan, Yakov Nekrich, Saladi Rahul, Konstantinos Tsakalidis:
Orthogonal point location and rectangle stabbing queries in 3-d. J. Comput. Geom. 13(1): 399-428 (2022) - [j103]Timothy M. Chan, Sariel Har-Peled, Mitchell Jones:
Optimal Algorithms for Geometric Centers and Depth. SIAM J. Comput. 51(3): 627-663 (2022) - [c157]Timothy M. Chan, Da Wei Zheng:
Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees. SODA 2022: 190-210 - [c156]Timothy M. Chan, Qizheng He, Subhash Suri, Jie Xue:
Dynamic Geometric Set Cover, Revisited. SODA 2022: 3496-3528 - [c155]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: 1501-1514 - [e3]Karl Bringmann, Timothy M. Chan:
5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022. SIAM 2022, ISBN 978-1-61197-706-6 [contents] - [i36]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 abs/2203.08356 (2022) - [i35]Timothy M. Chan, Da Wei Zheng:
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures. CoRR abs/2210.10172 (2022) - [i34]Timothy M. Chan:
Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs. CoRR abs/2211.05345 (2022) - 2021
- [j102]Timothy M. Chan, Sariel Har-Peled:
Smallest k-Enclosing Rectangle Revisited. Discret. Comput. Geom. 66(2): 769-791 (2021) - [j101]Timothy M. Chan, Qizheng He:
More dynamic data structures for geometric set cover with sublinear update time. J. Comput. Geom. 13(2): 90-114 (2021) - [j100]Timothy M. Chan, R. Ryan Williams:
Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. ACM Trans. Algorithms 17(1): 2:1-2:14 (2021) - [c154]Timothy M. Chan:
Faster Algorithms for Largest Empty Rectangles and Boxes. SoCG 2021: 24:1-24:15 - [c153]Timothy M. Chan, Qizheng He:
More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time. SoCG 2021: 25:1-25:14 - [c152]Timothy M. Chan:
All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error. ESA 2021: 27:1-27:9 - [c151]Timothy M. Chan, Zhengcheng Huang:
Dynamic Colored Orthogonal Range Searching. ESA 2021: 28:1-28:13 - [c150]Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu:
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths. ICALP 2021: 47:1-47:21 - [c149]Timothy M. Chan:
(Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems. SODA 2021: 1465-1482 - [c148]Timothy M. Chan:
Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices. SODA 2021: 1483-1495 - [c147]Timothy M. Chan, Saladi Rahul:
Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points. STACS 2021: 22:1-22:14 - [i33]Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu:
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths. CoRR abs/2102.06181 (2021) - [i32]Timothy M. Chan, Qizheng He:
More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time. CoRR abs/2103.07857 (2021) - [i31]Timothy M. Chan:
Faster Algorithms for Largest Empty Rectangles and Boxes. CoRR abs/2103.08043 (2021) - [i30]Timothy M. Chan, Qizheng He:
More on Change-Making and Related Problems. CoRR abs/2110.02503 (2021) - [i29]Timothy M. Chan, Qizheng He, Subhash Suri, Jie Xue:
Dynamic Geometric Set Cover, Revisited. CoRR abs/2111.01196 (2021) - [i28]Timothy M. Chan, Da Wei Zheng:
Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees. CoRR abs/2111.03744 (2021) - 2020
- [j99]Timothy M. Chan, Saladi Rahul, Jie Xue:
Range closest-pair search in higher dimensions. Comput. Geom. 91: 101669 (2020) - [j98]Timothy M. Chan:
Tree Drawings Revisited. Discret. Comput. Geom. 63(4): 799-820 (2020) - [j97]Timothy M. Chan:
Dynamic Geometric Data Structures via Shallow Cuttings. Discret. Comput. Geom. 64(4): 1235-1252 (2020) - [j96]Timothy M. Chan, Sariel Har-Peled, Mitchell Jones:
On Locality-Sensitive Orderings and Their Applications. SIAM J. Comput. 49(3): 583-600 (2020) - [j95]Timothy M. Chan:
More Logarithmic-factor Speedups for 3SUM, (median, +)-convolution, and Some Geometric 3SUM-hard Problems. ACM Trans. Algorithms 16(1): 7:1-7:23 (2020) - [c146]Timothy M. Chan, Qizheng He:
Faster Approximation Algorithms for Geometric Set Cover. SoCG 2020: 27:1-27:14 - [c145]Timothy M. Chan, Qizheng He, Yakov Nekrich:
Further Results on Colored Range Searching. SoCG 2020: 28:1-28:15 - [c144]Timothy M. Chan, Qizheng He:
More on Change-Making and Related Problems. ESA 2020: 29:1-29:14 - [c143]Timothy M. Chan, Zhengcheng Huang:
Improved Upper and Lower Bounds for LR Drawings of Binary Trees. GD 2020: 71-84 - [c142]Timothy M. Chan, Qizheng He:
Reducing 3SUM to Convolution-3SUM. SOSA 2020: 1-7 - [c141]Timothy M. Chan:
Dynamic Generalized Closest Pair: Revisiting Eppstein's Technique. SOSA 2020: 33-37 - [c140]Timothy M. Chan, Qizheng He:
On the Change-Making Problem. SOSA 2020: 38-42 - [c139]Timothy M. Chan, Yakov Nekrich:
Better Data Structures for Colored Orthogonal Range Reporting. SODA 2020: 627-636 - [c138]Josh Alman, Timothy M. Chan, R. Ryan Williams:
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions. SODA 2020: 637-649 - [c137]Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat:
Approximating text-to-pattern Hamming distances. STOC 2020: 643-656 - [i27]Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat:
Approximating Text-to-Pattern Hamming Distances. CoRR abs/2001.00211 (2020) - [i26]Timothy M. Chan, Qizheng He, Yakov Nekrich:
Further Results on Colored Range Searching. CoRR abs/2003.11604 (2020) - [i25]Timothy M. Chan, Qizheng He:
Faster Approximation Algorithms for Geometric Set Cover. CoRR abs/2003.13420 (2020)
2010 – 2019
- 2019
- [j94]Therese 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): 69-97 (2019) - [j93]Timothy M. Chan, Dimitrios Skrepetos:
Faster Approximate Diameter and Distance Oracles in Planar Graphs. Algorithmica 81(8): 3075-3098 (2019) - [j92]Timothy M. Chan, John Hershberger, Simon Pratt:
Two Approaches to Building Time-Windowed Geometric Data Structures. Algorithmica 81(9): 3519-3533 (2019) - [j91]Timothy M. Chan:
Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back. Discret. Comput. Geom. 61(4): 899-922 (2019) - [j90]Timothy M. Chan, Dimitrios Skrepetos:
All-Pairs Shortest Paths in Geometric Intersection Graphs. J. Comput. Geom. 10(1): 27-41 (2019) - [j89]Timothy M. Chan, Dimitrios Skrepetos:
Approximate shortest paths and distance oracles in weighted unit-disk graphs. J. Comput. Geom. 10(2): 3-20 (2019) - [j88]Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman, Aurélien Ooms:
Subquadratic encodings for point configurations. J. Comput. Geom. 10(2): 99-126 (2019) - [c136]Sergio Cabello, Timothy M. Chan:
Computing Shapley Values in the Plane. SoCG 2019: 20:1-20:19 - [c135]Timothy M. Chan, Sariel Har-Peled:
Smallest k-Enclosing Rectangle Revisited. SoCG 2019: 23:1-23:15 - [c134]Timothy M. Chan:
Dynamic Geometric Data Structures via Shallow Cuttings. SoCG 2019: 24:1-24:13 - [c133]Timothy M. Chan, Sariel Har-Peled, Mitchell Jones:
On Locality-Sensitive Orderings and Their Applications. ITCS 2019: 21:1-21:17 - [c132]Timothy M. Chan, Saladi Rahul, Jie Xue:
Range Closest-Pair Search in Higher Dimensions. WADS 2019: 269-282 - [c131]Timothy M. Chan, Yakov Nekrich, Michiel H. M. Smid:
Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles. WADS 2019: 283-295 - [e2]Timothy M. Chan:
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019. SIAM 2019, ISBN 978-1-61197-548-2 [contents] - [i24]Timothy M. Chan, Sariel Har-Peled:
Smallest k-Enclosing Rectangle Revisited. CoRR abs/1903.06785 (2019) - [i23]Timothy M. Chan:
Dynamic Geometric Data Structures via Shallow Cuttings. CoRR abs/1903.08387 (2019) - [i22]Timothy M. Chan, Saladi Rahul, Jie Xue:
Range closest-pair search in higher dimensions. CoRR abs/1905.01029 (2019) - [i21]Timothy M. Chan, Yakov Nekrich, Michiel H. M. Smid:
Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles. CoRR abs/1905.02322 (2019) - [i20]Timothy M. Chan, Zhengcheng Huang:
Improved Upper and Lower Bounds for LR Drawings of Binary Trees. CoRR abs/1912.10148 (2019) - 2018
- [j87]Zahed Rahmati, Timothy M. Chan:
A Clustering-Based Approach to Kinetic Closest Pair. Algorithmica 80(10): 2742-2756 (2018) - [j86]Timothy M. Chan, Zahed Rahmati:
An improved approximation algorithm for the discrete Fréchet distance. Inf. Process. Lett. 138: 72-74 (2018) - [j85]Timothy M. Chan:
Applications of Chebyshev polynomials to low-dimensional computational geometry. J. Comput. Geom. 9(2): 3-20 (2018) - [j84]Timothy M. Chan, Konstantinos Tsakalidis:
Dynamic Orthogonal Range Searching on the RAM, Revisited. J. Comput. Geom. 9(2): 45-66 (2018) - [j83]Timothy M. Chan, Yakov Nekrich:
Towards an Optimal Method for Dynamic Planar Point Location. SIAM J. Comput. 47(6): 2337-2361 (2018) - [j82]Timothy M. Chan, J. Ian Munro, Venkatesh Raman:
Selection and Sorting in the "Restore" Model. ACM Trans. Algorithms 14(2): 11:1-11:18 (2018) - [j81]Timothy M. Chan:
Improved Deterministic Algorithms for Linear Programming in Low Dimensions. ACM Trans. Algorithms 14(3): 30:1-30:10 (2018) - [c130]Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman, Aurélien Ooms:
Subquadratic Encodings for Point Configurations. SoCG 2018: 20:1-20:14 - [c129]Timothy M. Chan:
Tree Drawings Revisited. SoCG 2018: 23:1-23:15 - [c128]Timothy M. Chan, Dimitrios Skrepetos:
Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs. SoCG 2018: 24:1-24:13 - [c127]Timothy M. Chan, Konstantinos Tsakalidis:
Dynamic Planar Orthogonal Point Location in Sublogarithmic Time. SoCG 2018: 25:1-25:15 - [c126]Timothy M. Chan, Yakov Nekrich, Saladi Rahul, Konstantinos Tsakalidis:
Orthogonal Point Location and Rectangle Stabbing Queries in 3-d. ICALP 2018: 31:1-31:14 - [c125]Timothy M. Chan, Thomas C. van Dijk, Krzysztof Fleszar, Joachim Spoerhase, Alexander Wolff:
Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity. ISAAC 2018: 61:1-61:13 - [c124]Timothy M. Chan:
Approximation Schemes for 0-1 Knapsack. SOSA 2018: 5:1-5:12 - [c123]Timothy M. Chan:
More Logarithmic-Factor Speedups for 3SUM, (median, +)-Convolution, and Some Geometric 3SUM-Hard Problems. SODA 2018: 881-897 - [i19]Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman, Aurélien Ooms:
Subquadratic Encodings for Point Configurations. CoRR abs/1801.01767 (2018) - [i18]Timothy M. Chan:
Tree Drawings Revisited. CoRR abs/1803.07185 (2018) - [i17]Timothy M. Chan, Yakov Nekrich, Saladi Rahul, Konstantinos Tsakalidis:
Orthogonal Point Location and Rectangle Stabbing Queries in 3-d. CoRR abs/1805.08602 (2018) - [i16]Timothy M. Chan, Thomas C. van Dijk, Krzysztof Fleszar, Joachim Spoerhase, Alexander Wolff:
Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity. CoRR abs/1806.02851 (2018) - [i15]Timothy M. Chan, Sariel Har-Peled, Mitchell Jones:
On Locality-Sensitive Orderings and their Applications. CoRR abs/1809.11147 (2018) - 2017
- [j80]Timothy M. Chan, Meng He, J. Ian Munro, Gelin Zhou:
Succinct Indices for Path Minimum, with Applications. Algorithmica 78(2): 453-491 (2017) - [j79]Hicham El-Zein, Moshe Lewenstein, J. Ian Munro, Venkatesh Raman, Timothy M. Chan:
On the Succinct Representation of Equivalence Classes. Algorithmica 78(3): 1020-1040 (2017) - [j78]Timothy M. Chan, Zahed Rahmati:
Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points. Comput. Geom. 60: 2-7 (2017) - [j77]Timothy M. Chan, Dimitrios Skrepetos:
Dynamic data structures for approximate Hausdorff distance in the word RAM. Comput. Geom. 60: 37-44 (2017) - [j76]Peyman Afshani, Jérémy Barbay, Timothy M. Chan:
Instance-Optimal Geometric Algorithms. J. ACM 64(1): 3:1-3:38 (2017) - [j75]Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz, Timothy M. Chan, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Penny Haxell,