Haitao Wang

activity

20232026

collaborators

13 papers

cs.CG2026

Maximum Independent Sets in Disk Graphs with Disks in Convex Position

Anastasiia Tkachenko, Haitao Wang

For a set $D$ of disks in the plane, its disk graph $G (D)$ is the graph with vertex set $D$ , where two vertices are adjacent if and only if the corres…

cs.CG2026

Shortest Paths in Geodesic Unit-Disk Graphs

Bruce W. Brewer, Haitao Wang

Let $S$ be a set of $n$ points in a polygon $P$ with $m$ vertices. The geodesic unit-disk graph $G (S)$ induced by $S$ has vertex set $S$ and contains an edge between two vertices w…

cs.CG2026

An Optimal Algorithm for Computing Many Faces in Line Arrangements

Haitao Wang

Given a set of $m$ points and a set of $n$ lines in the plane, we consider the problem of computing the faces of the arrangement of the lines that contain at least one point. In th…

cs.CG2026

Computing Dominating Sets in Disk Graphs with Centers in Convex Position

Anastasiia Tkachenko, Haitao Wang

Given a set $P$ of $n$ points in the plane and a collection of disks centered at these points, the disk graph $G (P)$ has vertex set $P$ , with an edge between two vertices if their…

cs.CG2025

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs

Bruce W. Brewer, Haitao Wang

Given in the plane a set $S$ of $n$ points and a set of disks centered at these points, the disk graph $G (S)$ induced by these disks has vertex set $S$ and an edge between two vert…

cs.CG2025

Minimum-Weight Half-Plane Hitting Set

Gang Liu, Haitao Wang

Given a set $P$ of $n$ weighted points and a set $H$ of $n$ half-planes in the plane, the hitting set problem is to compute a subset $P^{'}$ of points from $P$ such that each half-pla…

cs.CG2025

An Optimal Algorithm for Half-plane Hitting Set

Gang Liu, Haitao Wang

Given a set $P$ of $n$ points and a set $H$ of $n$ half-planes in the plane, we consider the problem of computing a smallest subset of points such that each half-plane contains…

cs.CG2024

Dominating Set, Independent Set, Discrete $k$ -Center, Dispersion, and Related Problems for Planar Points in Convex Position

Anastasiia Tkachenko, Haitao Wang

Given a set $P$ of $n$ points in the plane, its unit-disk graph $G (P)$ is a graph with $P$ as its vertex set such that two points of $P$ are connected by an edge if their (Euclidea…

cs.CG2024

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs

Bruce W. Brewer, Haitao Wang

Let $V$ be a set of $n$ points in the plane. The unit-disk graph $G = (V, E)$ has vertex set $V$ and an edge $e_{uv} \in E$ between vertices $u, v \in V$ if the Euclidean distance…

cs.CG2024

Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems

Gang Liu, Haitao Wang

Given a set $P$ of $n$ points and a set $S$ of $m$ disks in the plane, the disk hitting set problem asks for a smallest subset of $P$ such that every disk of $S$ contains at least…

cs.CG2024

On Line-Separable Weighted Unit-Disk Coverage and Related Problems

Gang Liu, Haitao Wang

Given a set $P$ of $n$ points and a set $S$ of $n$ weighted disks in the plane, the disk coverage problem is to compute a subset of disks of smallest total weight such that the uni…

cs.CG2024

Algorithms for Computing Closest Points for Segments

Haitao Wang

Given a set $P$ of $n$ points and a set $S$ of $n$ segments in the plane, we consider the problem of computing for each segment of $S$ its closest point in $P$ . The previously best…

cs.CG2023

On the Line-Separable Unit-Disk Coverage and Related Problems

Gang Liu, Haitao Wang

Given a set $P$ of $n$ points and a set $S$ of $m$ disks in the plane, the disk coverage problem asks for a smallest subset of disks that together cover all points of $P$ . The prob…

Maximum Independent Sets in Disk Graphs with Disks in Convex Position

Shortest Paths in Geodesic Unit-Disk Graphs

An Optimal Algorithm for Computing Many Faces in Line Arrangements

Computing Dominating Sets in Disk Graphs with Centers in Convex Position

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs

Minimum-Weight Half-Plane Hitting Set

An Optimal Algorithm for Half-plane Hitting Set

Dominating Set, Independent Set, Discrete k-Center, Dispersion, and Related Problems for Planar Points in Convex Position

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs

Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems

On Line-Separable Weighted Unit-Disk Coverage and Related Problems

Algorithms for Computing Closest Points for Segments

On the Line-Separable Unit-Disk Coverage and Related Problems

Dominating Set, Independent Set, Discrete $k$ -Center, Dispersion, and Related Problems for Planar Points in Convex Position