On some partitioning problems for two-colored point sets

On some partitioning problems for two-colored point sets Clara I. Grima∗Carmen Hernando†¶ Clemens Huemer‡¶ Ferran Hurtado§¶ Abstract Let Sbe a two-colored set of npoints in general position in the plane. We show that Sadmits at least 2 n 17 pairwise disjoint monochromatic triangles with vertices in Sand empty of points of S. We further show that Scan be partitioned into 3 n 11 subsets with pairwise disjoint convex hull such that within each subset all but at most one point have the same color. A lower bound on the number of subsets needed in any such partition is also given. 1 Introduction An important class of problems in Computational Geometry deals with two-colored point sets [13] motivated, surely, by representing two different properties, facilities,... On the other hand, partitions of point sets have been the focus of an extensive research, see [8] for example. Regarding the union of both concepts, there can also be found results on partitioning a two-colored point set into monochromatic convex sets, that is, all points of a convex set belong to the same color class [10]. We study the following variants of this problem. In Section 2 we consider convex sets with a fixed number of vertices on its convex hull. In particular, we investigate how many monochromatic triangles can be found in a partition of S. Here, the monochromatic triangles do not contain points of Sin the interior. In Section 3 we consider partitions into “almost” monochromatic parts. For this case, the number of vertices on the convex hull of a part can be arbitrary, but in each convex set all but at most kof the points - the stainshave the same color, where kis a fixed value. This kind of study is potentially useful in noise reduction in digital signal processing [15]. Salt and pepper noise is a form of noise typically seen on images, where the image contains dark and white dots. Generally this type of noise will only affect a small number of image pixels. We derive bounds on the number of convex pieces that are needed for a partition of Sinto convex sets with at most one stain. A related problem on two-colored point sets (without considering convexity) is considered in [3], where the authors look for geometric monochromatic 2-factors, possibly adding some extra Steiner points. 2 Disjoint monochromatic triangles Given a two-colored point set Sof npoints in general position in the plane, let κ(S, m) be the maximum number of monochromatic convex m-gons that can be constructed with vertices in S, such that their convex hulls are pairwise disjoint and have interiors empty of points from S. Let κ(n, m) = min{κ(S, m)|S⊂R2is in general position,|S|=n}. ∗Departamento de Matem´atica Aplicada I, Universidad de Sevilla [email protected], Partially supported by projects MTM2008-05866-C03-01 and P06-FQM-01649 †Departament de Matem`atica Aplicada I, Universitat Polit`ecnica de Catalunya, [email protected] ‡Departament de Matem`atica Aplicada IV, Universitat Polit`ecnica de Catalunya, [email protected] §Departament de Matem`atica Aplicada II, Universitat Polit`ecnica de Catalunya, [email protected] ¶Partially supported by projects MEC MTM2006-01267 and DURSI 2005SGR00692 For m= 2, κ(S, 2) is the number of segments in the largest noncrossing matching in Ssuch that every edge connects points of the same color. Dumitrescu and Steiger proved that there are sets of npoints in general position such that any monochromatic matching consists of fewer than (1 −ǫ)n/2 edges, for some constant ǫand gave a lower bound for the constant [11], later improved by Dumitrescu and Kaye [9] who showed 3n/7−O(1) ≤κ(n, 2) ≤47n/95 + O(1). For m= 4 it has been conjectured that κ(S, 4) ≥1 provided that |S|is large enough [7]; an example of 32 points with no monochromatic empty convex quadrilateral was given in [16]. Only recently it has been shown that each set of at least 5044 two-colored points contains an (not necessarily convex) empty monochromatic quadrilateral [2]. Arbitrarily large two-colored sets without monochromatic empty convex pentagons were described in [7], therefore κ(n, m) = 0 for all m≥5. Here we focus on the number κ(n, 3). As every set of 10 points contains an empty convex pentagon, and at least three of its vertices will have the same color, we immediately get jn 10k≤κ(n, 3). A related result was proved in [7]: every two-colored set of npoints in general position admits ⌈n/4⌉ − 2 empty monochromatic compatible triangles, which is tight, where compatible means that any two of them have disjoint interiors and, for example all of them might share a vertex. For κ(n, 3) we require a much stronger disjointness condition. Let us recall a result that will be used repeatedly later: Lemma 2.1. [12] Let Sbe a set of npoints in general position in the plane, and let Gxbe the graph with vertex set S, two of them being adjacent when the line they define has exactly n−2 2points on one side and n−2 2on the other side. Then, for any nodd, the graph Gxis connected. We are now ready for proving the main result of this section: Theorem 2.2. Let κ(n, 3) be the largest number such that any two-colored set of npoints in general position in the plane admits κ(n, 3) triangles with vertices in S, pairwise disjoint and empty of points of S. Then we have 2jn 17k≤κ(n, 3) ≤   n−2 6if nis even n−1 6if nis odd Proof. We first show that any set S9of 9 black and white points contains an empty monochromatic triangle. Let Wdenote the set of white points, Bthe set of black points, and assume |W|>|B|. Wadmits a triangulation into 2|W| − |conv(W)| − 2 white triangles with pairwise disjoint interiors; conv(W) denotes the convex hull of W. If |W| ≥ 6 or |conv(W)|= 3 then the triangulation of W contains at least one white triangle also empty of black points. Assume that there is no triangulation of Wthat contains a triangle empty of points of B. This implies that |W|= 5 and |conv(W)| ≥ 4.If |conv(W)|= 5 then at least 3 black points lie in the interior of conv(W) and form at least one empty triangle. Finally, if |conv(W)|= 4 then the 4 black points lie in the interior of conv(W). Triangulating Bwe obtain at least two black triangles, at most one of them contains a white point in its interior. We now show that any set S17 of 17 black and white points contains two pairwise disjoint empty monochromatic triangles. This immediately implies the lower bound. Thereto, we use that S17 admits a segment joining one point of each color and leaving 8 points on one side and 7 on the other. Indeed, for each of the 17 points there exists another point of the set such that the line they define leaves 8 points on one side and 7 on the other. By Lemma 2.1, the graph defined by all these line segments is connected. Consequently not all of these line segments connect two points of the same color. Let xand ydenote the two points of S17 of such a separating line segment, where xand yhave different color. There is an empty monochromatic triangle in the set formed by the set of 7 points together with {x, y}. Since xand yhave different color, this triangle uses at most one of xand y. Assume yis not used. We thus can find another empty monochromatic triangle in the set formed by the 8 points together with y. These two triangles are pairwise disjoint. To prove the upper bound, consider the set in Figure 1. The set Wof white points is in convex position and no two of them lie on a horizontal line. Near every white point, but the topmost and lowermost, a black point is placed such that it lies on the horizontal line through the white point and in the interior of conv(W). Then this n-point set has no empty white triangle, because each white triangle can be stabbed by a horizontal line through its second white point, ordered by y-coordinates, thus containing a black point. Then, there are n−2 6pairwise disjoint black triangles. For the case nis odd, remove the topmost white point in Figure 1. We remark that this example also appears in problems related to guarding triangles [6]. Figure 1: A point set Swith κ(S, 3) = ⌊|S|−2 6⌋. 3 At most one stain Given a two-colored point set Sof npoints in general position in the plane, let σ(S, k) be the minimum number of subsets in a partition of S, such that their convex hulls are pairwise disjoint and all the points in each subset have the same color with the possible exception of at most kof them (the “stains”). Let σ(n, k) = max{σ(S, k)|S⊂R2is in general position,|S|=n}. For k= 0, σ(S, 0) is the cardinality of the smallest partition of Sinto monochromatic subsets whose convex hulls are pairwise disjoint. Dumitrescu and Pach [10] proved that σ(n, 0) = n+ 1 2. For generic kthere is a trivial bound σ(n, k)≤n 2k+ 1, because every subset of 2k+ 1 points has at most kstains. Here we focus on the number σ(n, 1) and prove the following result: Theorem 3.1. Let σ(n, 1) be the smallest number such that any two-colored set of npoints in general position in the plane can be partitioned into σ(n, 1) subsets with pairwise disjoint convex hulls, each one having at most one stain. Then we have n+ 1 4≤σ(n, 1) ≤     3n 11 if n′= 0 3n 11 +ln′+1 4mif n′6= 0 where n′is the residue of dividing nby 11. Figure 2: A point set Swith σ(S, 1) = (|S|+ 2)/4. Proof. For the lower bound, we first consider the case nis even. Let Sbe a two-colored set of npoints in convex position such that any two neighbored points on the convex hull have different colors, see Figure 2. We show that σ(S, 1) ≥n+1 4.Let Π be a partition of Sinto the minimum number of subsets, such that their convex hulls are pairwise disjoint and such that each subset contains at most one stain. Define a directed tree T, whose nodes are the subsets of Π, as follows: Choose some subset Bsof Π as the source vertex of T. Draw directed arcs from Bsto all subsets of Π that can be “seen” from Bs, and take each of these subsets as the root of a subtree, defined iteratively. More formally, a subset Biis a descendant of Bsif conv(Bs∪Bi) does not intersect any other subsets. Similarly, a subset Bjis a descendant of a subset Bk6=Bsif Bkis a descendant of some subset Bh,Bjis not a descendant of Bhand conv(Bk∪Bj) does not intersect any other subsets of Π. Figure 3 shows an example. Assume that Π contains at least one subset Bsthat contains at least four points, as the statement is obviously true otherwise. Choose Bsas the root of T. Bs Figure 3: A partition of Sand the associated directed tree. Let nkdenote the number of interior nodes of Tthat correspond to subsets of Π containing exactly kpoints, and let hdenote the number of leaves of T. Note that an interior node of Tcorresponds to a subset of Π of at least two points, and a leaf of Tcorresponds to a subset of Π of at most three points. In the following we give a lower bound on hin terms of the number of interior nodes of T. Thereto, we assign each leaf of Tto a unique interior node of T, where a leaf ℓcan be assigned to an interior node vif there is a directed path from vto ℓin T. We define this assignment recursively by first assigning leaves to the source vertex Bsand then considering the assignment for the children of Bs.A subset of Π contains at most two edges of the convex hull. We thus can assign at least |Bs| − 2 leaves to Bs.For k≥5, to each subset Bp6=Bsof Π containing kpoints assign at least k−4 leaves: Bphas at least k−3 outgoing edges in T, where one of them is counted for a leaf assigned to an antecessor of Bp. We thus obtain h≥n5+ 2n6+ 3n7+···+ (t−4)nt+ 2,(1) where tis the number of points of the largest subset, and the last summand 2 comes from the two additional leaves assigned to Bs. On the other hand, the number of leaves of Tis at least h≥n−2n2−3n3−4n4− · · · − tnt 3.(2) Taking the sum of (1) and three times (2) we obtain 4h≥n−2n2−3n3−4n4−4n5−4n6− · · · − 4nt+ 2. Thus, we also have 4h≥n−4n2−4n3−4n4−4n5−4n6− · · · − 4nt+ 2, which implies that σ(S, 1) ≥h+n2+n3+n4+···+nt≥n+ 2 4=n+ 1 4, because nis even. The case when nis odd can be treated the same way, just remove one point from S, apply the bound for the obtained even point set and add the removed point to a piece. For the upper bound, we first show that σ(S7,1) ≤2. Any set S7of 7 black and white points admits a segment joining one point of each color leaving 3 points on one side and 2 on the other. Indeed, for each of the 7 points there exists another point of the set such that the line they define leaves 3 points on one side and 2 on the other. By Lemma 2.1, the graph defined by all these line segments is connected. Consequently not all of these line segments connect two points of the same color. Then, the 3 points on one side of the segment together with one of the endpoints of the segment form a piece with at most one stain. The remaining three points form the other piece of the partition. We are going to prove now that for any set S11 of 11 black and white points we have σ(S11,1) ≤3; from this and σ(S7,1) ≤2 the upper bound is immediately derived. Let Wand Bbe the set of white and black points in S11, respectively, and let us assume, without loss of generality, that |W|>|B|. If |B| ≤ 3, the claim is obvious; if |B|= 4 we can always find two black points b1and b2such that the other two black points lie in opposite halfplanes with respect to the line b1b2; then the two sets of white and black points lying in the same halfplane and {b1, b2}give the claimed partition. Therefore, we are only left with the case |B|= 5. For the case |B|= 5 observe that whenever we can separate with a line a set of four points with at most one stain, then the seven remaining points would require at most two pieces and we would be done. Let us consider first the case in which at least one of the white points, w, is an extreme point, and let us denote by x1,...,x10 the other points in counterclockwise radial order around w, in such a way that x1and x10 are neighbors of won the convex hull conv(S11). Assume that the set {x1, x2, x3}contains exactly two black points and one white point, as otherwise we would be done, because we would be able to isolate the subset {w, x1, x2, x3}with at most one stain. For the same reason we assume that x4is a white point, as otherwise we could separate the subset {x1, x2, x3, x4}. By symmetry reasons we also assume that {x8, x9, x10}contains exactly two black points and one white point and that x7 is a white point. But now {x5, x6}must consist of one white point and one black point, and we can take the partition {x1, x2, x3},{w, x4, x5, x6, x7},{x8, x9, x10}(Figure 4). Let us switch to the case in which none of the white points is an extreme point. If there are four or five black points that are extreme, we are done, because we can define two black monochromatic w x x   Figure 4: The case |B|= 5 with at least one white extreme point. subsets by taking the endpoints of two disjoint convex hull edges, and the remaining black point would join as a stain the whole subset of white points. Hence we are left with the situation in which the convex hull is a triangle with three black corners, which we denote by {b1, b2, b3}. The line through the other two black points, b4and b5, will cut two convex hull edges; for ease of description we assume that the line b1b2is the horizontal base of the convex hull and that the line b4b5is parallel to b1b2, which is no restriction of generality from the combinatorial viewpoint (refer to Figure 5). x  x  b b x  b b bx  x  b b x  b b bx  x  b b x  b b b (a) (b) (c) Figure 5: The cases |B|= 5 with no white extreme point. If the halfplane above the line b4b5contains less than two white points, we can separate them together with b4,b5and b3, and get σ(S11,1) = 3; the same happens if the halfplane above the line b4b5contains more than two white points, which we would separate together with b3. Let us assume therefore that there are exactly two white points above b4b5. If the triangle b3b4x2contains at most one of them we can take it as part together with b4,b5and b3, a second part would consist of b1and any white point interior to b1b4b3and a third part would consist of b2and any white point interior to the quadrilateral b1b2x2b4(Figure 5(a)), this gives σ(S11,1) = 3. The same argument applies to the triangle b5b3x1, hence we assume hereafter that the two white points above b4b5lie inside the triangle b3b4b5. Now, if the triangle b1b4b3contains at most one white point, we can take it together with b1, b4and b3as a part, a second part would consist of b5and the two white points above b4b5, and a third part would consist of b2and all the white points inside the quadrilateral b1b2x2b4; again, we get σ(S11,1) = 3 (Figure 5(b)). The same reasoning as in the preceding paragraph applies to the triangle b5b2b3, hence we are finally left with the situation in which two white points are interior to b1b4x1, two are interior to b5b2x2and two are interior to b3b4b5(Figure 5(c)). Now we can take b1and b3together with the white point closest to the line b1b3, the other white point inside b1b4b3joins b2and b4in a second subset, and the white points interior to b3b4b2together with b5is the third part. Again, we get σ(S11,1) = 3, which concludes the proof. 4 Future work We have presented some combinatorial studies on κ(n, 3) (the number of monochromatic empty disjoint triangles in any two–colored n–set) and σ(n, 1) (the smallest number of pieces with at most one stain in any two–colored n-set), so an algorithmic approach to both problems would be interesting. On the other hand, since in the first case we have that that any two–colored n–set admits a triangulation containing at least 2 n 17 monochromatic triangles, one can be interested, thinking in interpolation problems, in to decide, given a two–colored n–set of points, whether there exists a triangulation of it without monochromatic triangles. Our first steps in this direction lead us to suspect that this will be an NP–complete problem. A related question to determine κ(n, 3) is to count the number of all (not necessarily disjoint) monochromatic empty triangles in a two-colored point set. This problem has been addressed in [1, 14]. While for uncolored point sets there always exists a quadratic number of empty triangles [4], determining the right asymptotic value for the two-colored case represents an intriguing open problem. Acknowledgments We thank Merc`e Claverol, Alberto M´arquez, Carlos Seara and David Wood for useful discussions on the topic considered in this paper. References [1] O. Aichholzer, R. Fabila-Monroy, D. Flores-Pe˜naloza, T. Hackl, C. Huemer, J. Urrutia, Empty monochromatic triangles, 20th Canadian Conference on Computational Geometry, 75–78, 2008. [2] O. Aichholzer, T. Hackl, C. Huemer, F. Hurtado, B. Vogtenhuber, Large bi-colored point sets admit empty monochromatic 4-gons, 25th European Workshop on Computational Geometry, 133–136, 2008. [3] M.N. Atienza, C. Cort´es, D. Garijo, M.A. Garrido, C.I. Grima, A. M´arquez, M.A. Moreno, J.R. Portillo, P. Reyes, R. Robles, M.E. Su´arez, J. Valenzuela, M.T. Villar, k-Factores en nubes bicrom´aticas, XII Encuentros de Geometr´ıa Computacional, Valladolid, 53–57, 2007. [4] I. B´ar´any, Z. F¨uredi, Empty simplices in Euclidean space, Canadian Mathematical Bulletin 30, 436–445, 1987. [5] P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer-Verlag, New York, 2005. [6] J. Czyzowicz, E. Kranakis, J. Urrutia, Guarding the Convex Subsets of a Point Set, 12th Canadian Conference on Computational Geometry, 47–50, 2000. [7] O. Devillers, F. Hurtado, G. K´arolyi, C. Seara, Chromatic variants of the Erd˝os-Szekeres Theorem, Computational Geometry: Theory and Applications 26, 193–208, 2003. [8] R. Ding, K. Hosono, M. Urabe and C. Xu Partitioning a Planar Point Set into Empty Convex Polygons, Lecture Notes in Computer Science 2866, 129–134, 2003. [9] A. Dumitrescu, R. Kaye, Matching colored points in the plane: some new results, Computational Geometry: Theory and Applications 19, 69–85, 2001. [10] A. Dumitrescu, J. Pach, Partitioning colored point sets into monochromatic parts, International Journal of Computational Geometry and Applications 12, 401–412, 2002. [11] A. Dumitrescu, W. Steiger, On a matching problem in the plane, Discrete Mathematics 211, 183–195, 2000. [12] P. Erd˝os, L. Lov´asz, A. Simmons, E. G. Straus, Dissection graphs of planar point sets, in A Survey of Combinatorial Theory, (J.N. Srivastava et al., eds.), North-Holland, 139–149, 1973. [13] A. Kaneko, M. Kano, Discrete geometry on red and blue points in the plane – A survey, in Discrete and Computational Geometry, The Goodman–Pollack Festschrift, Algorithms and Combinatorics 25, (B. Aronov et al., eds.), Springer-Verlag, 551–570, 2003. [14] J. Pach, G. T´oth, Monochromatic empty triangles in two-colored point sets, in Geometry, Games, Graphs and Education, The Joe Malkevitch Festschrift, (S. Garfunkel, R. Nath, eds.), COMAP, 195–198, 2008. [15] A. Rosenfeld, Picture Processing by Computer, New York: Academic Press, 1969. [16] R. Van Gulik, 32 Two-Colored Points with No Empty Monochromatic Convex Fourgons, Geombinatorics XV, 32–33, 2005.