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

Gang Liu, Haitao Wang

Introduction

The disk coverage problem is a fundamental challenge in computational geometry: given a set of points and a set of weighted disks, the goal is to find a subset of disks with minimum total weight that covers all points. While the general version is NP-hard, specific geometric constraints allow for efficient exact algorithms. In a recent breakthrough, Liu and Wang presented a subquadratic algorithm for the line-separable weighted unit-disk coverage problem, improving the best-known runtime from $O(n^2 \log n)$ to $O(n^{3/2} \log^2 n)$.

Problem Definition: Line-Separable Unit Disks

The paper focuses on a specific variant defined by two constraints:

  1. Unit-Disk: All disks have an identical radius.
  2. Line-Separable: There exists a line $\ell$ such that all points lie on one side and all disk centers lie on the opposite side.
Line-separable unit-disk configuration

This configuration allows for a structured approach to coverage that breaks the complexity of the general case. Breaking the "quadratic barrier" for this problem has been a significant goal in algorithmic efficiency for geometric optimization.

Algorithmic Framework

The authors achieve their results through a highly optimized Dynamic Programming (DP) implementation supported by three key pillars:

1. Reduction to 1D Interval Coverage

Building on established techniques, the authors demonstrate that the 2D problem can be mapped to a 1D interval coverage problem. By sorting points along the line $\ell$, they define a DP state where $DP[i]$ represents the optimal cost to cover the first $i$ points.

2. Geometric Duality

To manage the disks efficiently, the problem is transformed into a dual space. In this setting, disks are represented as points and points as disks, enabling the application of advanced point-location and range-searching techniques to find optimal coverage candidates.

3. Hierarchical $(1/r)$-Cuttings

The core innovation lies in the use of hierarchical cuttings to accelerate DP transitions. Standard DP would require a linear scan for each step, leading to an $O(n^2)$ bottleneck. By partitioning the plane into "cells" (pseudo-trapezoids), the authors can manage costs at a cell level rather than at the individual disk level.

Pseudo-trapezoid cell

This structure ensures that only a small fraction of disk boundaries cross any given cell, allowing for efficient FindMinCost and ResetCost operations.

Key Results and Complexity Improvements

The proposed algorithm provides significant speedups across several related geometric problems. By balancing the cutting parameter $r$ (setting $r = \sqrt{m}$), the authors achieve the following complexity bounds:

Problem Previous Best This Paper
Line-Separable Weighted Unit-Disk Coverage $O(n^2 \log n)$ $O(n^{3/2} \log^2 n)$
General Halfplane Coverage $O(n^4 \log n)$ $O(n^{7/2} \log^2 n)$
Lower-only Halfplane Coverage $O(n^2 \log n)$ $O(n^{3/2} \log^2 n)$
Line-Separable Weighted Hitting Set $O(n^2 \log n)$ $O(n^{3/2} \log^2 n)$

The symmetry of unit disks also allows the coverage algorithm to be applied directly to the Hitting Set problem, where one seeks the minimum weight points to "hit" every disk.

Conclusion and Future Directions

While the subquadratic result is a major theoretical milestone, the authors note that hierarchical cuttings are complex to implement and their benefits may only manifest at very large scales. Furthermore, the algorithm relies strictly on the line-separable and unit-disk constraints.

Future research may explore whether the weighted version can reach the near-linear complexity ($O(n \log n)$) currently possible for the unweighted case, or if $O(n^{1.5})$ represents a fundamental lower bound for this specific approach.

Summary updated

BibTeX
@inproceedings{liu2024line,
  author = {Gang Liu and Haitao Wang},
  title = {{On Line-Separable Weighted Unit-Disk Coverage and Related Problems}},
  booktitle = {Comput. Geom},
  year = {2024},
}
Figure