15 citations · 74 across the 39 of their papers we have counts for
4 papers · 1 filter
Improved Algorithms for the Bichromatic Two-Center Problem for Pairs of Points
Haitao Wang, Jie Xue
We consider a bichromatic two-center problem for pairs of points. Given a set of pairs of points in the plane, for every pair, we want to assign a red color to one point an…
A Linear-Time Algorithm for Radius-Optimally Augmenting Paths in a Metric Space
Christopher Johnson, Haitao Wang
Let be a path graph of vertices embedded in a metric space. We consider the problem of adding a new edge to to minimize the radius of the resulting graph. Previously, a…
Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs
Haitao Wang, Jie Xue
We revisit a classical graph-theoretic problem, the \textit{single-source shortest-path} (SSSP) problem, in weighted unit-disk graphs. We first propose an exact (and deterministic)…
A Divide-and-Conquer Algorithm for Two-Point Shortest Path Queries in Polygonal Domains
Haitao Wang
Let be a polygonal domain of holes and vertices. We study the problem of constructing a data structure that can compute a shortest path between and in…