Home Bookmarks Papers Blog

# Computing Optimal Kernels in Two Dimensions

$\newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}} \newcommand{\CH}{\Mh{\mathsf{ch}}} \newcommand{\CHX}{\CH\pth{#1}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\PS}{\Mh{P}}% \newcommand{\PSA}{\Mh{Q}}% \newcommand{\CS}{\Mh{C}}% \newcommand{\Mh}{#1} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$
Pankaj K. Agarwal and Sariel Har-Peled.
Let $\PS$ be a set of $n$ points in $\reals^2$. A subset $\CS\subseteq \PS$ is an \emph{$\eps$-kernel} of $\PS$ if the projection of the convex hull of $\CS$ approximates that of $\PS$ within $(1-\eps)$-factor in every direction. The set $\CS$ is a \emph{weak $\eps$-kernel} if its directional width approximates that of $\PS$ in every direction. We present fast algorithms for computing a minimum-size $\eps$-kernel as well as a weak $\eps$-kernel. We also present a fast algorithm for the Hausdorff variant of this problem. In addition, we introduce the notion of \emph{$\eps$-core}, a convex polygon lying inside $\CHX{\PS}$, prove that it is a good approximation of the optimal $\eps$-kernel, present an efficient algorithm for computing it, and use it to compute an $\eps$-kernel of small size.
PDF. : arXiv.
Last modified: Wed 2022-07-20 18:21:33 UTC 2022 by Sariel Har-Peled