On balanced 4-holes in bichromatic point sets
On balanced 4-holes in bichromatic point sets
复制标题
双色点集中的平衡四孔
DOI：
10.1016/j.comgeo.2014.09.004
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Inmaculada Ventura
中科院分区：
文献类型：
--
作者：
Sergey Bereg;Jose-Miguel Diaz-Banez;Ruy Fabila-Monroy;Pablo Perez-Lantero;Adriana Ramirez-Vigueras;Toshinori Sakai;Jorge Urrutia;Inmaculada Ventura
设S= R ∈ B是平面上一般位置的点集，使其每个元素都被着色为红色或蓝色，其中R和B分别表示着色为红色和蓝色的点。顶点在S中的四边形称为4-洞，如果它的内部没有S的元素。我们说S的一个4-洞是平衡的，如果它有S的2个红点和2个蓝点作为顶点。本文证明了：若R和B各含n个点，则S至少有n2 - 4 n12个平衡4-洞，且此界紧到常数因子.由于存在不具有平衡凸4-洞的双色点集，我们进一步给出了具有这类4-洞的双色点集的一个刻画。
Abstract Let S= R∪ B be a point set in the plane in general position such that each of its elements is colored either red or blue, where R and B denote the points colored red and the points colored blue, respectively. A quadrilateral with vertices in S is called a 4-hole if its interior is empty of elements of S. We say that a 4-hole of S is balanced if it has 2 red and 2 blue points of S as vertices. In this paper, we prove that if R and B contain n points each then S has at least n 2− 4 n 12 balanced 4-holes, and this bound is tight up to a constant factor. Since there are two-colored point sets with no balanced convex 4-holes, we further provide a characterization of the two-colored point sets having this type of 4-holes.