3 papers
cs.DS2025
Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
We give the first truly subquadratic time algorithm, with running time, for computing the diameter of an -vertex unit-disk graph, resolving a central open prob…
cs.DS2025
Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
Gramoz Goranci, Peter Kiss, Neel Patel +3
We consider the Euclidean bi-chromatic matching problem in the dynamic setting, where the goal is to efficiently process point insertions and deletions while maintaining a high-qua…
cs.CG2022
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…