论文标题
公正代表的几何系统
Geometric Systems of Unbiased Representatives
论文作者
论文摘要
令$ p $为$ \ m athbb {r}^d $，$ b $的一组点。 $ \ oo $的对象与$ b $相对于$ b $的每个颜色数量相同，称为$ b $。对于$ p $的$ \ b $的$ \ b $，一个无偏见的代表（g-sur）的几何系统是子集$ \ oo'\ subseteq \ oo $ $，因此，对于任何$ \ b $的$ b $ of $ \ b $都可以在$ \ oo'$中平衡$ b $ b $。 我们研究寻找G-Surs的问题。我们获得了由间隔，尺寸限制间隔，轴平行盒和欧几里得球组成的G-Surs尺寸的一般边界。我们表明，即使在一条线和间隔范围内的点的简单情况下，G-SUR问题也是NP-HARD。此外，我们研究了一个相关的问题，即确定实际分布和着色最大和最小平衡间隔的大小。 我们的结果是Balachandran等人发起的作品的几何环境的自然扩展。关于公正代表的任意系统。
Let $P$ be a set of points in $\mathbb{R}^d$, $B$ a bicoloring of $P$ and $\Oo$ a family of geometric objects (that is, intervals, boxes, balls, etc). An object from $\Oo$ is called balanced with respect to $B$ if it contains the same number of points from each color of $B$. For a collection $\B$ of bicolorings of $P$, a geometric system of unbiased representatives (G-SUR) is a subset $\Oo'\subseteq\Oo$ such that for any bicoloring $B$ of $\B$ there is an object in $\Oo'$ that is balanced with respect to $B$. We study the problem of finding G-SURs. We obtain general bounds on the size of G-SURs consisting of intervals, size-restricted intervals, axis-parallel boxes and Euclidean balls. We show that the G-SUR problem is NP-hard even in the simple case of points on a line and interval ranges. Furthermore, we study a related problem on determining the size of the largest and smallest balanced intervals for points on the real line with a random distribution and coloring. Our results are a natural extension to a geometric context of the work initiated by Balachandran et al. on arbitrary systems of unbiased representatives.
