Computing Optimal Kernels in Two Dimensions

Let $P$ be a set of $n$ points in $\mathbb{R}^2$. A subset $C\subseteq P$ is an $\varepsilon$-kernel of $P$ if the projection of the convex hull of $C$ approximates that of $P$ within $(1-\varepsilon)$-factor in every direction. The set $C$ is a weak $\varepsilon$-kernel if its directional width approximates that of $P$ in every direction. We present fast algorithms for computing a minimum-size $\varepsilon$-kernel as well as a weak $\varepsilon$-kernel. We also present a fast algorithm for the Hausdorff variant of this problem. In addition, we introduce the notion of $\varepsilon$-core, a convex polygon lying inside $CH(P)$, prove that it is a good approximation of the optimal $\varepsilon$-kernel, present an efficient algorithm for computing it, and use it to compute an $\varepsilon$-kernel of small size.