论文标题
计算二维的最佳内核
Computing Optimal Kernels in Two Dimensions
论文作者
论文摘要
令$ p $为$ \ re^2 $中的$ n $点。对于参数$ \ varepsilon \在（0,1）$中，子集$ c \ subseteq p $是$ p $的\ emph {$ \ varepsilon $ -Kernel}，如果$ c $ c $ c $ of $ c $ of $ c $ of $ p $ of $ p $（1- \ varepsilon $ in Doriestion）的co $ c $ co $ interiesition的$ p $。 $ c $是$ p $的a \ emph {弱$ \ varepsilon $ -kernel}，如果其方向宽度近似于每个方向的$ p $。令$ \ Mathsf {k} _ {\ varepsilon}（p）$（resp。\ $ \ \ $ \ \ \ \ \ \ \ \ \ \ \ {k}^{\ mathsf {\ mathsf {w}} _ {\ varepsilon}（p）$表示$ \ varepsilon $ $ -kern $ -kern $ -kernel（p）$。 $ P $。我们提出一个$ O（N \ Mathsf {K} _ {\ Varepsilon}（p）\ log n）$ - 计算$ \ varepsilon $ -Kernel的时间算法，$ p $的$ p $ size $ \ \ mathsf {k}用于计算弱$ \ varepsilon $ -kernel的算法$ p $ size $ {\ mathsf {k}}}^{\ mathsf {w}} _ {\ varepsilon}（p）$。我们还为此问题的Hausdorff变体提供了一种快速算法。 In addition, we introduce the notion of \emph{$\varepsilon$-core}, a convex polygon lying inside $\mathsf{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小尺寸。
Let $P$ be a set of $n$ points in $\Re^2$. For a parameter $\varepsilon\in (0,1)$, a subset $C\subseteq P$ is an \emph{$\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 \emph{weak $\varepsilon$-kernel} of $P$ if its directional width approximates that of $P$ in every direction. Let $\mathsf{k}_{\varepsilon}(P)$ (resp.\ $\mathsf{k}^{\mathsf{w}}_{\varepsilon}(P)$) denote the minimum-size of an $\varepsilon$-kernel (resp. weak $\varepsilon$-kernel) of $P$. We present an $O(n\mathsf{k}_{\varepsilon}(P)\log n)$-time algorithm for computing an $\varepsilon$-kernel of $P$ of size $\mathsf{k}_{\varepsilon}(P)$, and an $O(n^2\log n)$-time algorithm for computing a weak $\varepsilon$-kernel of $P$ of size ${\mathsf{k}}^{\mathsf{w}}_{\varepsilon}(P)$. We also present a fast algorithm for the Hausdorff variant of this problem. In addition, we introduce the notion of \emph{$\varepsilon$-core}, a convex polygon lying inside $\mathsf{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.
