On balanced 4-holes in bichromatic point sets

摘要

Let S=R boolean OR 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)-4n/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. (C) 2014 Elsevier B.V. All rights reserved.