论文标题
加权的Epsilon网络
Weighted Epsilon-Nets
论文作者
论文摘要
由Bukh和Nivasch最近在单面$ \ Varepsilon $ -Approximant上进行的工作，我们介绍了\ emph {加权$ \ varepsilon $ -nets}的概念。对于$ \ mathbb {r}^d $中的点集的几何概念，类似于$ \ varepsilon $ -nets和$ \ varepsilon $ -Approximations，它比前者更强，并且比后者更弱。主要的想法是，小型集可以包含许多点，而大型集合必须包含加权$ \ varepsilon $ -NET的许多点。 在本文中，我们分析了较弱的加权$ \ varepsilon $ -net，相对于凸组和轴平行的盒子，并在$ \ varepsilon $上提供了$ \ varepsilon $ \ varepsilon $ nets的上限和下限，尺寸为第二和三。其中一些范围也适用于经典的$ \ varepsilon $ -net。
Motivated by recent work of Bukh and Nivasch on one-sided $\varepsilon$-approximants, we introduce the notion of \emph{weighted $\varepsilon$-nets}. It is a geometric notion of approximation for point sets in $\mathbb{R}^d$ similar to $\varepsilon$-nets and $\varepsilon$-approximations, where it is stronger than the former and weaker than the latter. The main idea is that small sets can contain many points, whereas large sets must contain many points of the weighted $\varepsilon$-net. In this paper, we analyze weak weighted $\varepsilon$-nets with respect to convex sets and axis-parallel boxes and give upper and lower bounds on $\varepsilon$ for weighted $\varepsilon$-nets of size two and three. Some of these bounds apply to classical $\varepsilon$-nets as well.
