Fast Approximation Algorithms for Piercing Boxes by Points

2023/11/03 by Pankaj K. Agarwal, Agarwal, Pankaj K., Sariel Har-Peled +5 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.2311.02050

Abstract

\newcommand\poptp \newcommand\Reℝ\newcommand\NN \newcommand\BXB \newcommand\bbb \newcommand\epsε \newcommand\polylogpolylog Let B=\b₁, … ,b_n\ be a set of n axis-aligned boxes in \Re^d where d≥2 is a constant. The piercing problem is to compute a smallest set of points \N ⊂ \Re^d that hits every box in B, i.e., \N∩ b_i≠ ∅, for i=1,…, n. Let \popt=\popt(B), the piercing number be the minimum size of a piercing set of B. We present a randomized O(d²loglog \popt)-approximation algorithm with expected running time O(n^d/2\polylog n). Next, we present a faster O(n^{log d+1})-time algorithm but with a slightly inferior approximation factor of O(2^4dloglog\popt). The running time of both algorithms can be improved to near-linear using a sampling-based technique, if \popt = O(n^1/d). For the dynamic version of the problem in the plane, we obtain a randomized O(loglog\popt)-approximation algorithm with O(n^1/2\polylog n ) amortized expected update time for insertion or deletion of boxes. For squares in \Re², the update time can be improved to O(n^1/3\polylog n ).

Cited by

• Approximating Euclidean Shallow-Light Trees
• Hitting Geodesic Intervals in Structurally Restricted Graphs

Related

• Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
• Lower bounds for piercing and coloring boxes
• Piercing All Translates of a Set of Axis-Parallel Rectangles
• Faster Approximation Algorithms for Geometric Set Cover
• Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions