Geometric hitting set for line-constrained disks

DOI10.1007/978-3-031-38906-1_38arXiv2305.09045MaRDI QIDQ6139038FDOQ6139038

Author name not available (Why is that?)

Publication date: 16 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Given a set

P

of

n

weighted points and a set

S

of

m

disks in the plane, the hitting set problem is to compute a subset

P^{'}

of points of

P

such that each disk contains at least one point of

P^{'}

and the total weight of all points of

P^{'}

is minimized. The problem is known to be NP-hard. In this paper, we consider a line-constrained version of the problem in which all disks are centered on a line

e l l

. We present an

O ((m + n) l o g (m + n) + k a p p a l o g m)

time algorithm for the problem, where

k a p p a

is the number of pairs of disks that intersect. For the unit-disk case where all disks have the same radius, the running time can be reduced to

O ((n + m) l o g (m + n))

. In addition, we solve the problem in

O ((m + n) l o g (m + n))

time in the

L_{i n f t y}

and

L_{1}

metrics, in which a disk is a square and a diamond, respectively. Our techniques can also be used to solve other geometric hitting set problems. For example, given in the plane a set