Geometric hitting set for line-constrained disks

DOI10.1007/978-3-031-38906-1_38MaRDI QIDQ6139038FDO

Authors

Publication date 16 January 2024

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

Full work available at URL https://arxiv.org/abs/2305.09045

zbMATH Keywords

diskscoveragehitting setline-constrained

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

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^{\prime }$ of points of $P$ such that each disk contains at least one point of $P^{\prime }$ and the total weight of all points of $P^{\prime }$ 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 $ell$. We present an $O((m+n)log(m+n)+kappalogm)$ time algorithm for the problem, where $kappa$ 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)log(m+n))$. In addition, we solve the problem in $O((m+n)log(m+n))$ time in the $L_{infty}$ 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 $P$ of $n$ weighted points and a set $S$ of $n$ half-planes, we solve in $O(n^{4}logn)$ time the problem of finding a minimum weight hitting set of $P$ for $S$. This improves the previous best algorithm of $O(n^6)$ time by nearly a quadratic factor.

Cites work

• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• Algorithms for the line-constrained disk coverage and related problems
• Algorithms – ESA 2005
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Fast Algorithms for Finding Nearest Common Ancestors
• Fractional cascading. I: A data structuring technique
• Hitting sets when the VC-dimension is small
• Improved results on geometric hitting set problems
• Minimum-cost coverage of point sets by disks
• PTAS for geometric hitting set problems via local search
• Practical and efficient algorithms for the geometric hitting set problem
• Reducibility among combinatorial problems
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• The implicit hitting set approach to solve combinatorial optimization problems with an application to multigenome alignment

This page was built for publication: Geometric hitting set for line-constrained disks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139038)