Da Wei Zheng

ICML Conference 2025 Conference Paper

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time

• Gramoz Goranci
• Peter Kiss
• Neel Patel
• Martin P. Seybold
• Eva Szilagyi
• Da Wei Zheng

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-quality solution. Computing the minimum cost bi-chromatic matching is one of the core problems in geometric optimization that has found many applications, most notably in estimating Wasserstein distance between two distributions. In this work, we present the first fully dynamic algorithm for Euclidean bi-chromatic matching with sublinear update time. For any fixed $\varepsilon > 0$, our algorithm achieves $O(1/\varepsilon)$-approximation and handles updates in $O(n^{\varepsilon})$ time. Our experiments show that our algorithm enables effective monitoring of the distributional drift in the Wasserstein distance on real and synthetic data sets, while outperforming the runtime of baseline approximations by orders of magnitudes.

SODA Conference 2025 Conference Paper

Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decrementai reachability, and more

• Adam Karczmarz
• Da Wei Zheng

Le and Wulff-Nilsen [SODA ’24] initiated a systematic study of VC set systems to unweighted K h -minor-free directed graphs. We extend their results in the following ways: • We present the first application of VC set systems for real-weighted minor-free digraphs to build the first exact subquadratic-space distance oracle with O (log n ) query time. Prior work using VC set systems only applied in unweighted and integer-weighted digraphs. • We describe a unified system for analyzing the VC dimension of balls and the LP set system (based on Li- Parter [STOC ’19]) of Le-Wulff-Nilsen [SODA ’24] using pseudodimension. This is a major conceptual contribution that allows for both improving our understanding of set systems in digraphs as well as improving the bound of the LP set system in directed graphs to h — 1. • We present the first application of these set systems in a dynamic setting. Specifically, we construct decremental reachability oracles with subquadratic total update time and constant query time. Prior to this work, it was not known if this was possible to construct oracles with subquadratic total update time and polylogarithmic query time, even in planar digraphs. • We describe subquadratic time algorithms for unweighted digraphs including (1) constructions of exact distance oracles, (2) computation of vertex eccentricities and Wiener index. The main innovation in obtaining these results is the use of dynamic string data structures.

FOCS Conference 2025 Conference Paper

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension

• Timothy M. Chan
• Hsien-Chih Chang
• Jie Gao 0001
• Sándor Kisfaludi-Bak
• Hung Le 0001
• Da Wei Zheng

We give the first truly subquadratic time algorithm, with ${O^{\ast}}\left( {{n^{2 - 1/18}}} \right)$ running time, for computing the diameter of an n-vertex unit-disk graph, resolving a central open problem in the literature. Our result is obtained as an instance of a general framework, applicable to different graph families and distance problems. Surprisingly, our framework completely bypasses sublinear separators (or r-divisions) which were used in all previous algorithms. Instead, we use low-diameter decompositions in their most elementary form. We also exploit bounded VC-dimension of set systems associated with the input graph, as well as new ideas on geometric data structures. Among the numerous applications of the general framework, we obtain: 1)An $\tilde O\left( {m{n^{1 - 1/(2d)}}} \right)$ time algorithm for computing the diameter of m-edge sparse unweighted graphs with constant VC-dimension d. The previously known algorithms by Ducoffe, Habib, and Viennot [SODA 2019] and Duraj, Konieczny, and Potępa [ESA 2024] are truly subquadratic only when the diameter is a small polynomial. Our result thus generalizes truly subquadratic time algorithms known for planar and minor-free graphs (in fact, it slightly improves the previous time bound for minor-free graphs). 2)An $\tilde O\left( {{n^{2 - 1/12}}} \right)$ time algorithm for computing the diameter of intersection graphs of axis-aligned squares with arbitrary size. The best-known algorithm by Duraj, Konieczny, and Potępa [ESA 2024] only works for unit squares and is only truly subquadratic in the low-diameter regime. 3)The first algorithms with truly subquadratic complexity for other distance-related problems, including all-vertex eccentricities, Wiener index, and exact distance oracles. In particular, we obtain the first exact distance oracle with truly subquadratic space and $\tilde O(1)$ query time for any sparse graph with bounded VC-dimension, again generalizing previous results for planar and minor-free graphs.

SODA Conference 2024 Conference Paper

An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism

• Timothy M. Chan
• Pingan Cheng
• Da Wei Zheng

SODA Conference 2024 Conference Paper

Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs

• Yi-Jun Chang
• Da Wei Zheng

We consider the massively parallel computation (MPC) model, which is a theoretical abstraction of large- scale parallel processing models such as MapReduce. In this model, assuming the widely believed 1-vs-2-cycles conjecture, solving many basic graph problems in O (1) rounds with a strongly sublinear memory size per machine is impossible. We improve on the recent work of Holm and Tětek [SODA 2023] that bypass this barrier for problems when a planar embedding of the graph is given. In the previous work, on graphs of size n with O(n/S) machines, the memory size per machine needs to be at least S = n 2/3+Ω(1), whereas we extend their work to the fully scalable regime, where the memory size per machine can be S = n δ for any constant 0 < δ < 1. We thus give the first constant round fully scalable algorithms for embedded planar graphs for the problems of (i) connectivity and (ii) minimum spanning tree (MST). Moreover, we show that the ɛ-emulator of Chang, Krauthgamer, and Tan [STOC 2022] can be incorporated into our recursive framework to obtain constant-round (1 + ɛ)-approximation algorithms for the problems of computing (iii) single source shortest path (SSSP), (iv) global min-cut, and (v) st -max flow. All previous results on cuts and flows required linear memory in the MPC model. Furthermore, our results give new algorithms for problems that implicitly involve embedded planar graphs. We give as corollaries of our result the constant round fully scalable algorithms for (vi) 2D Euclidean MST using O ( n ) total memory and (vii) (1 + ɛ)-approximate weighted edit distance using Õ(n 2-δ ) memory. Our main technique is a recursive framework combined with novel graph drawing algorithms that allow us to compute smaller embedded planar graphs in constant rounds in the fully scalable setting. * The full version of the paper can be accessed at https: //arxiv. org/abs/2304. 07441

SODA Conference 2023 Conference Paper

Halving by a Thousand Cuts or Punctures

• Sariel Har-Peled
• Da Wei Zheng

For point sets P 1, …, P k, a set of lines L is halving if any face of the arrangement A ( L ) contains at most | P i |/2 points of P i, for all i. We study the problem of computing a halving set of lines of minimal size. Surprisingly, we show a polynomial time algorithm that outputs a halving set of size O (ø 3/2 ), where θ is the size of the optimal solution - this is of interest when ø = o (log 2 n ). Our solution relies on solving a new variant of the weak ε-net problem for corridors, which we believe to be of independent interest. We also study other variants of this problem, including an alternative “dual” settings, where one needs to introduce a set of guards (i. e. , points), such that no convex set avoiding the guards contains more than half the points of each point set.

SODA Conference 2023 Conference Paper

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 multiple logarithmic factors that were caused by the use of multi-level data structures. Highlights include the following: • For a set of n points in a constant dimension d, we give data structures with O ( n d ) (or slightly better) space that can answer simplex range counting queries in optimal O (log n ) time and simplex range reporting queries in optimal O (log n + k ) time, where k denotes the output size. For semigroup range searching, we obtain O (log n ) query time with O(n d polylog n ) space. Previous data structures with similar space bounds by Matoušek from nearly three decades ago had O (log d +1 n ) or O (log d +1 n + k ) query time. • For a set of n simplices in a constant dimension d, we give data structures with O ( n ) space that can answer stabbing counting queries (counting the number of simplices containing a query point) in O ( n 1-1/ d ) time, and stabbing reporting queries in O(n 1-1/d + k ) time. Previous data structures had extra log d n factors in space and query time. • For a set of n (possibly intersecting) line segments in 2D, we give a data structure with O ( n ) space that can answer ray shooting queries in time. This improves Wang's recent data structure [SoCG'20] with O(n log n ) space and query time. * The full version of the paper can be accessed at https: //arxiv. org/abs/2210. 10172

SODA Conference 2022 Conference Paper

Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees

• Timothy M. Chan
• Da Wei Zheng

We revisit Hopcroft's problem and related fundamental problems about geometric range searching. Given n points and n lines in the plane, we show how to count the number of point-line incidence pairs or the number of point-above-line pairs in O ( n 4/3 ) time, which matches the conjectured lower bound and improves the best previous time bound of n 4/3 2 O (log ∗ n ) obtained almost 30 years ago by Matoušek. We describe two interesting and different ways to achieve the result: the first is randomized and uses a new 2D version of fractional cascading for arrangements of lines; the second is deterministic and uses decision trees in a manner inspired by the sorting technique of Fredman (1976). The second approach extends to any constant dimension. Many consequences follow from these new ideas: for example, we obtain an O ( n 4/3 )-time algorithm for line segment intersection counting in the plane, O ( n 4/3 )-time randomized algorithms for bichromatic closest pair and Euclidean minimum spanning tree in three or four dimensions, and a randomized data structure for halfplane range counting in the plane with O ( n 4/3 ) preprocessing time and space and O ( n 1/3 ) query time.