Balanced intervals of two stes of points on a line or circle

Balanced Intervals of Two Sets of Points on a line or circle Atsushi Kaneko aand M. Kano b aDepartment of Computer Science and Communication Engineering Kogakuin University, Nishi-Shinjuku, Shinjuku-ku, Tokyo, 163-8677, Japan bDepartment of Computer and Information Sciences Ibaraki University, Hitachi, Ibaraki, 316-8511, Japan [email protected]araki.ac.jp http://gorogoro.cis.ibaraki.ac.jp Abstract Let n, m, k, h be positive integers such that 1 ≤n≤m, 1 ≤k≤nand 1 ≤h≤m. Then we give a necessary and sufficient condition for every configuration with nred points and mblue points on a line or circle to have an interval containing precisely kred points and hblue points. Key words: balanced interval, interval, two sets of points, line, circle 1. A balanced interval on a line In this section we shall prove the following theorem. Theorem 1 Let n, m, k, h be integers such that 1≤n≤m,1≤k≤nand 1≤h≤m. Then for any nred points and mblue points on a line in general position (i.e., no two points lie on the same position.), there exists an interval that contains precisely kred points and hblue points if and only if j n k+ 1k+ 1(h−1) < m < j n k−1k(h+ 1), (1) where the rightmost term is an infinite number when k= 1. We begin with an example of our theorem. Consider a configuration consisting of 10 red points and 20 blue points on a line in general position. Then by the above theorem, we can easily show that if k∈ {1,2,3,5,10}, then such a configuration has an interval containing exactly kred points and 2k blue points; otherwise (i.e., k∈ {4,6,7,8,9}) there exist a configuration that has no such an interval (Fig. 1). We call an interval that contains given number of red points and blue points a balanced interval. (a): (b): Red points = Blue points = Fig. 1. (a): An interval containing 3 red points and 6 blue points; (b): A configuration that has no interval containing exactly 4 red points and 8 blue points. Theorem 1 is an easy consequence of the following five lemmas. For a configuration with red and blue points on a line, we denote by Rand Bthe sets of red points and blue points, respectively. A configuration X with nred points and mblue points on the line is expressed as {x1} ∪ {x2} ∪ · · · ∪ {xn+m}, 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry where each xidenotes a red point or a blue point ordered from left to right. The configuration Xis also expressed as R(1) ∪B(1) ∪ · · · ∪ R(s)∪B(s), where R(i) and B(i) denote disjoint subsets of R and B, respectively, and some of them may be empty sets. For a set Y, we denote by |Y|the cardinality of Y. Lemma 2 If m≤j n k+ 1k+ 1(h−1),(2) then there exists a configuration with nred points and mblue points that has no interval containing exactly kred points and hblue points. PROOF. Let t=⌊n k−1⌋. Then n≤(t+1)(k−1), and m≥t(h+ 1) by (4). Hence we can obtain the following configuration with nred points and m blue points: R(1) ∪B(1) ∪ · · · ∪ R(t+ 1) ∪B(t+ 1), where |R(i)| ≤ k−1 for every 1 ≤i≤t+1, |R(1)∪ · · ·∪R(t+1)|=n,|B(i)|=h+1 for every 1 ≤i≤ t,|B(t+ 1)|=m−(h+ 1)t≥0 and |B(1) ∪ · · · ∪ B(t+ 1)|=m. Then this configuration obviously has no interval containing exactly kred points and hblue points since every interval containing kred points must include B(j) for some 1 ≤j≤t. Lemma 3 If m > j n k+ 1k+ 1(h−1),(3) then every configuration with nred points and m blue points on a line has an interval containing exactly kred points and at least hblue points. PROOF. Let t=⌊n k+1 ⌋. Let Xbe a configuration with nred points and mblue points. Suppose that Xhas no desired interval. Namely, we assume that every interval containing exactly kred points has at most h−1 blue points. Let r1, r2,··· , rnbe the red points of Xordered from left to right. For integers 1 ≤i < j≤n, let I(i, j) denote an open interval (ri, rj), and let B(i, j) denote the set of blue points contained in I(i, j). Furthermore, B(−∞, i) denotes the set of blue points contained in the open interval (−∞, ri), and B(i, ∞) is defined analogously. Then for any integer 1 ≤s≤t−1, I(s(k+1),(s+1)(k+ 1)) contains exactly kred points {rj|s(k+1)+1 ≤ j≤(s+1)(k+1)−1)}, and thus |B(s(k+1),(s+ 1)(k+ 1))| ≤ h−1 by our assumption. Similarly, an open interval (−∞, rk+1) contains exactly kred points, and thus |B(−∞, k + 1)| ≤ h−1. Moreover, since n < (t+ 1)(k+ 1), I(t(k+ 1),∞) has at most kred points, and thus B(t(k+1),∞)≤h−1. Therefore |B| ≤ |B(−∞, k + 1) ∪B(k+ 1,2(k+ 1)) ∪ · · · ∪B(t(k+ 1),∞)| ≤(t+ 1)(h−1). This contradicts (3). Consequently the lemma is proved. Lemma 4 If 2≤kand m≥jn k−1k(h+ 1),(4) then there exists a configuration with nred points and mblue points on a line that has no interval containing exactly kred points and hblue points. PROOF. Let t=⌊n k−1⌋. Then n≤(t+1)(k−1), and m≥t(h+ 1) by (4). Hence we can obtain the following configuration with nred points and m blue points: R(1) ∪B(1) ∪ · · · ∪ R(t+ 1) ∪B(t+ 1), where |R(i)| ≤ k−1 for every 1 ≤i≤t+1, |R(1)∪ · · ·∪R(t+1)|=n,|B(i)|=h+1 for every 1 ≤i≤ t,|B(t+ 1)|=m−(h+ 1)t≥0 and |B(1) ∪ · · · ∪ B(t+ 1)|=m. Then this configuration obviously has no interval containing exactly kred points and hblue points since every interval containing kred points must include B(j) for some 1 ≤j≤t. Lemma 5 If 2≤kand m < jn k−1k(h+ 1),(5) then every configuration with nred points and m blue points on a line has an interval containing exactly kred points and at most hblue points. PROOF. Let t=⌊n k−1⌋. Let Xbe a configuration with nred points and mblue points. Suppose that Xhas no desired interval. Namely, we assume March 25-26, 2004 Seville (Spain) that every interval containing exactly kred points has at least h+ 1 blue points. Let r1, r2,··· , rnbe the red points of Xordered from left to right. For integers 1 ≤i < j ≤n, let I[i, j], denote a closed interval [ri, rj], and let B′(i, j) denote the set of blue points contained in I[i, j]. Then for any integer 0 ≤s≤t−2, I[k+s(k− 1), k + (s+ 1)(k−1)] contains exatly kred points {rj|k+s(k−1) ≤j≤k+ (s+ 1)(k−1))}, and thus |B′(k+s(k−1), k + (s+ 1)(k−1))| ≥ h+ 1 by our assumption. Similarly, we have |B′(1, k)| ≥ h+ 1. Therefore |B| ≥ |B′(1, k)∪B′(k, k + (k−1)) ∪ · · · ∪B′(k+ (t−2)(k−1), k + (t−1)(k−1))| ≥t(h+ 1). This contradicts (5). Consequently the lemma is proved. Lemma 6 Consider a configuration with nred points and mblue points on a line. Suppose that there exists two intervals Iand Jsuch that both I and Jcontain exactly kred points respectively, I contains at most hblue points, and that Jcontains at least hblue points. Then there exists an interval that contains exactly kred points and hblue points. PROOF. If the sets of red points contained in I and J, respectively, are the same, then the lemma immediately follows. Thus we may assume that I∩ R6=J∩R, where Rdenote the set of nred points. Without loss of generality, we may assume that the leftmost red point of Ilies to the left of J. We shall show that we can move Ito Jstep by step in such a way that the number of red points is a constant kand the number of blue points changes ±1 at each step. We first remove the blue points left to the leftmost red point of Ione by one, and then add the consecutive blue points lying to the right of Ione by one, and denote the resulting interval by I1(Fig. 3). We next simultaneously remove the leftmost red point of I1and add the red point lying to the right of I1, and get an interval I2, which also contains exactly kred points and whose blue points are the same as those in I1(Fig. 3). By repeating this procedure, we can get an interval whose red point set is equal to that of J. Therefore, we can move Ito Jin the desired way. Consequently, we can find the required interval, which contains exactly kred points and hblue points. 2. A balanced interval on a circle (a) (b) Red points = Blue points = Fig. 2. (a): An interval containing 4 red points and 8 blue points; (b): A configuration that has no interval containing exactly 4 red points and 5 blue points. In this section, we consider the following theorem, and give its example in Figure reffig:2 Theorem 7 Let n, m, k, h be integers such that 1≤n≤m,1≤k≤nand 1≤h≤m. Then for any nred points and mblue points on a circle in general position (i.e., no two points lie on the same position.), there exists an interval that con- 20th European Workshop on Computational Geometry tains precisely kred points and hblue points if and only if n k+ 1(h−1) < m < n k−1(h+ 1),(6) where the rightmost term is an infinite number when k= 1. Theorem 8 can be proved by showing similar lemmas as in the case of line. We conclude the paper by the next conjecture. Conjecture 8 Let n, m, k, h be integers such that 1≤n≤m,1≤k≤nand 1≤h≤m. Then for any nred points and mblue points in the plane in general position (i.e., no three points lie on the same.), there exists a wedge that contains precisely kred points and hblue points if and only if n k+ 2(h−1) < m < n k−2(h+ 1),(7) where the rightmost term is an infinite number when k= 1. P r1 r2 P (a) (b) r1 r2 Fig. 3. Wedges containing 4 red points and 8 blue points. References [1] B´ar´any, I., and Matouˇsek, J.; Simultaneous partitions of measures by k-fans, Discrete Comput. Geom. 25 (2001)317–334. [2] Goodman, J. and O’Rourke, J.; Handbook of Discrete and Computational Geometry, CRC Press, (1997) . [3] Kaneko, A. and Kano, M.; Discrete geometry on red and blue points in the plane — A survey, Discrete and Computational Geometry・The Goodman-Pollack Festschrift・With contributions by numerous experts (Springer) (2003) 551-570.