8 citations · 31 across the 25 of their papers we have counts for
43 papers
Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size
Timothy M. Chan, Zhengcheng Huang
In SoCG 2022, Conroy and Tóth presented several constructions of sparse, low-hop spanners in geometric intersection graphs, including an -size 3-hop spanner for dis…
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
In this paper we carefully combine Fredman's trick [SICOMP'76] and Matoušek's approach for dominance product [IPL'91] to obtain powerful results in fine-grained complexity: - Under…
Minimum Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem
Timothy M. Chan
We present a (combinatorial) algorithm with running time close to for computing the minimum directed Hausdorff distance between two sets of points under tra…
Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs
Timothy M. Chan
We consider problems related to finding short cycles, small cliques, small independent sets, and small subgraphs in geometric intersection graphs. We obtain a plethora of new resul…
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures
Timothy M. Chan, Da Wei Zheng
We revisit the classic problem of simplex range searching and related problems in computational geometry. We present a collection of new results which improve previous bounds by mu…
Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
The SUM hypothesis, the APSP hypothesis and SETH are the three main hypotheses in fine-grained complexity. So far, within the area, the first two hypotheses have mainly been abo…