Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems
<|reference_start|>Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems: 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 one point in the subset. The problem is NP-hard. In this paper, we consider a line-constrained version in which all disks have their centers on a line. We present an $O(m\log^2n+(n+m)\log(n+m))$ time algorithm for the problem. This improves the previously best result of $O(m^2\log m+(n+m)\log(n+m))$ time for the weighted case of the problem where every point of $P$ has a weight and the objective is to minimize the total weight of the hitting set. Our algorithm actually solves a more general line-separable problem with a single intersection property: The points of $P$ and the disk centers are separated by a line $\ell$ and the boundary of every two disks intersect at most once on the side of $\ell$ containing $P$.<|reference_end|>
@article{liu2024unweighted,
    title={Unweighted Geometric Hitting Set for Line-Constrained Disks and Related
  Problems},
    author={Gang Liu, Haitao Wang},
    journal={arXiv preprint arXiv:2407.00331},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.00331},
    primaryClass={cs.CG cs.DS}
}