Stabbing pairwise intersecting disks by five points
$
\newcommand{\Re}{\mathbb{R}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\SetX}{\mathsf{X}}
\newcommand{\rad}{r}
\newcommand{\Mh}[1]{#1}
\newcommand{\query}{q}
\newcommand{\eps}{\varepsilon}
\newcommand{\VorX}[1]{\mathcal{V} \pth{#1}}
\newcommand{\Polygon}{\mathsf{P}}
\newcommand{\IntRange}[1]{[ #1 ]}
\newcommand{\Space}{\overline{\mathsf{m}}}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\pt}{p}
\newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|}
\newcommand{\ptq}{q}
\newcommand{\pts}{s}$
Sariel Har-Peled,
Haim Kaplan,
Wolfgang Mulzer,
Liam Roditty,
Paul Seiferth,
Micha Sharir, and
Max Willert.
We present an $O(n)$ expected time algorithm and an $O(n \log n)$
deterministic algorithm to find a set of five points that stab a
set of $n$ pairwise intersecting disks in the plane. We also give
a simple construction with 13 pairwise intersecting disks that
cannot be stabbed by three points.
PDF.
:
arXiv
:
DBLP.
Last modified: Mon 2022-07-25 15:08:29 UTC 2022 by Sariel Har-Peled