15 citations · 74 across the 39 of their papers we have counts for
41 papers · 1 filter
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…
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…
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…
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…
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…
Algorithms for Covering Multiple Barriers
Shimin Li, Haitao Wang
In this paper, we consider the problems for covering multiple intervals on a line. Given a set of line segments (called "barriers") on a horizontal line and another set…
Quickest Visibility Queries in Polygonal Domains
Haitao Wang
Let be a point in a polygonal domain of holes and vertices. We consider a quickest visibility query problem. Given a query point in , t…
Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane
Haitao Wang
Given a rectilinear domain of pairwise-disjoint rectilinear obstacles with a total of vertices in the plane, we study the problem of computing bicriteria rect…
Linear Time Approximation Schemes for Geometric Maximum Coverage
Kai Jin, Jian Li, Haitao Wang +2
We study approximation algorithms for the following geometric version of the maximum coverage problem: Let be a set of weighted points in the plane. Let repre…