Fast Approximation Algorithms for Piercing Boxes by Points Article Swipe

MAKE IMPACT

Pankaj K. Agarwal , Sariel Har-Peled , Rahul Raychaudhury , Stavros Sintos · YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2311.02050

$\newcommand{\popt}{\mathcal{p}} \newcommand{\Re}{\mathbb{R}}\newcommand{\N}{\mathcal{N}} \newcommand{\BX}{\mathcal{B}} \newcommand{\bb}{\mathsf{b}} \newcommand{\eps}{\varepsilon} \newcommand{\polylog}{\mathrm{polylog}} $ Let $\mathcal{B}=\{\mathsf{b}_1, \ldots ,\mathsf{b}_n\}$ be a set of $n$ axis-aligned boxes in $\Re^d$ where $d\geq2$ is a constant. The \emph{piercing problem} is to compute a smallest set of points $\N \subset \Re^d$ that hits every box in $\mathcal{B}$, i.e., $\N\cap \mathsf{b}_i\neq \emptyset$, for $i=1,\ldots, n$. Let $\popt=\popt(\mathcal{B})$, the \emph{piercing number} be the minimum size of a piercing set of $\mathcal{B}$. We present a randomized $O(d^2\log\log \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^{4d}\log\log\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(\log\log\popt)$-approximation algorithm with $O(n^{1/2}\polylog n )$ amortized expected update time for insertion or deletion of boxes. For squares in $\Re^2$, the update time can be improved to $O(n^{1/3}\polylog n )$.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2311.02050

PDF

https://arxiv.org/pdf/2311.02050

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4388444886

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4388444886

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2311.02050

Digital Object Identifier

Title

Fast Approximation Algorithms for Piercing Boxes by Points

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2023

Year of publication

Publication date

2023-11-03

Full publication date if available

Authors

Pankaj K. Agarwal, Sariel Har-Peled, Rahul Raychaudhury, Stavros Sintos

List of authors in order

Landing page

https://arxiv.org/abs/2311.02050

Publisher landing page

PDF URL

https://arxiv.org/pdf/2311.02050

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2311.02050

Direct OA link when available

Concepts

Combinatorics, Multiplicative function, Mathematics, Omega, Running time, Binary logarithm, Approximation algorithm, Algorithm, Physics, Mathematical analysis, Quantum mechanics

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload