Home Bookmarks Papers Blog

# Computing Optimal Kernels in Two Dimensions

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.