2024/06/29 by Liu, Gang, Wang, Haitao · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2407.00331
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(mlog2n+(n+m)log(n+m)) time algorithm for the problem. This improves the previously best result of O(m2log 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 ℓ and the boundary of every two disks intersect at most once on the side of ℓ containing P.