15 citations · 74 across the 39 of their papers we have counts for
49 papers
Deterministic Distance Selection in Time
Haitao Wang
Let be a set of points in the plane. Given an integer with , the distance selection problem asks for the -th smallest distance among all pair…
Shortest Path Map Equivalence Decompositions and Applications
Haitao Wang
Given a polygonal domain in the plane, the shortest path map with respect to a point , denoted by , is the decomposition of into cells such that shortest paths f…
Improved Algorithms for Distance Selection and Related Problems
Haitao Wang, Yiming Zhao
In this paper, we propose new techniques for solving geometric optimization problems involving interpoint distances of a point set in the plane. Given a set of points in th…
Geometric Hitting Set for Line-Constrained Disks and Related Problems
Gang Liu, Haitao Wang
Given a set of weighted points and a set of disks in the plane, the hitting set problem is to compute a subset of points of such that each disk contains at…
Dynamic Convex Hulls under Window-Sliding Updates
Haitao Wang
We consider the problem of dynamically maintaining the convex hull of a set of points in the plane under the following special sequence of insertions and deletions (called {\em…
Computing the Minimum Bottleneck Moving Spanning Tree
Haitao Wang, Yiming Zhao
Given a set of points that are moving in the plane, we consider the problem of computing a spanning tree for these moving points that does not change its combinatorial stru…
Unit-Disk Range Searching and Applications
Haitao Wang
Given a set of points in the plane, we consider the problem of computing the number of points of in a query unit disk (i.e., all query disks have the same radius). We s…
A Simple Algorithm for Computing the Zone of a Line in an Arrangement of Lines
Haitao Wang
Let be a set of lines in the plane. The zone of a line in the arrangement of is the set of faces of whose closure int…
Constructing Many Faces in Arrangements of Lines and Segments
Haitao Wang
We present new algorithms for computing many faces in arrangements of lines and segments. Given a set of lines (resp., segments) and a set of points in the plane, t…
Algorithms for the Line-Constrained Disk Coverage and Related Problems
Logan Pedersen, Haitao Wang
Given a set of points and a set of weighted disks in the plane, the disk coverage problem asks for a subset of disks of minimum total weight that cover all points o…
Reverse Shortest Path Problem for Unit-Disk Graphs
Haitao Wang, Yiming Zhao
Given a set P of n points in the plane, the unit-disk graph G_{r}(P) with respect to a parameter r is an undirected graph whose vertex set is P such that an edge connects two point…
An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons
Haitao Wang
Given a set of point sites in a simple polygon of vertices, we consider the problem of computing the geodesic farthest-point Voronoi diagram for in . It is k…
A New Algorithm for Euclidean Shortest Paths in the Plane
Haitao Wang
Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational g…
Algorithms for Diameters of Unicycle Graphs and Diameter-Optimally Augmenting Trees
Haitao Wang, Yiming Zhao
We consider the problem of computing the diameter of a unicycle graph (i.e., a graph with a unique cycle). We present an O(n) time algorithm for the problem, where n is the number…
Shortest Paths Among Obstacles in the Plane Revisited
Haitao Wang
Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational g…
A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space
Haitao Wang, Yiming Zhao
Let be a path graph of vertices embedded in a metric space. We consider the problem of adding a new edge to so that the radius of the resulting graph is minimized, wher…
Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments
Haitao Wang
In this paper, we first consider the subpath convex hull query problem: Given a simple path of vertices, preprocess it so that the convex hull of any query subpath of c…
On the Planar Two-Center Problem and Circular Hulls
Haitao Wang
Given a set of points in the Euclidean plane, the two-center problem is to find two congruent disks of smallest radius whose union covers all points of . Previously, Epp…
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…
An -Time Algorithm for the k-Center Problem in Trees
Haitao Wang, Jingru Zhang
We consider a classical k-center problem in trees. Let T be a tree of n vertices and every vertex has a nonnegative weight. The problem is to find k centers on the edges of T such…
Covering Uncertain Points in a Tree
Haitao Wang, Jingru Zhang
In this paper, we consider a coverage problem for uncertain points in a tree. Let T be a tree containing a set P of n (weighted) demand points, and the location of each demand poin…