On Triangular Separation of Bichromatic Point Sets Helena Bergold, Arun Kumar Das, Robert Lauff, Manfred Scheucher, Felix Schröder, Marie Diana Sieper Abstract We address the problem of computing the minimum number of triangles to separate a set of blue points from a set of red points in ℝ 2 \mathbb{R}^{2} . A set of triangles is a separator of one color from the other if every point of that color is contained in some triangle and no triangle contains points of both colors. We consider all possible variants of the problem depending on whether the triangles are allowed to overlap or not and whether all points or just the blue points need to be contained in a triangle. We show that computing the minimum cardinality triangular separator of a set of blue points from a set of red points is NP-hard and further investigate worst case bounds on the minimum cardinality of triangular separators for a bichromatic set of n n points. 1 Introduction Separability problems on colored point sets are concerned with computing a class of objects of given shapes for a given set of colored points, such that every point of a fixed color is covered with the computed objects and no object contains points of different colors. The exact problem varies depending on the underlying optimizing criteria. We study triangles separating red and blue points in \mathbb{R}^{2} . Separating red and blue points from each other is well studied in computational geometry under the name class cover problems [ 2 , 4 , 7 ] due to their wide applications in data mining, pattern recognition, learning theory, and operations research. The problem is formally defined as follows: Problem 1 ( Overlap-Separation ) . Input: A set of red and blue points P in \mathbb{R}^{2} . Output: A minimum set \mathcal{T} of triangles containing all points such that no member of \mathcal{T} contains points of both colors. Note that this problem can be subdivided into two problems. First find the minimum number of triangles \mathcal{T}_{b} containing all the blue points in P such that no triangle in \mathcal{T}_{b} contains a red point. Then compute the minimum number of triangles \mathcal{T}_{r} containing the red, but no blue points. The set \mathcal{T}_{b}\cup\mathcal{T}_{r} is an optimal solution for Problem 1 . Thus it is enough to solve this: Problem 2 ( Overlap-Separation-of-blue ) . Input: A set of red and blue points P in \mathbb{R}^{2} . Output: A minimum set \mathcal{T} of triangles containing all blue but no red points of P . However once the triangles are not allowed to intersect each other, the problem becomes more restricted and spawns two different problems for separating the points as follows. Problem 3 ( Disjoint-Separation ) . Input: A set of red and blue points P in \mathbb{R}^{2} . Output: A minimum set \mathcal{T} of disjoint triangles containing all points such that no member of \mathcal{T} contains points of both colors. Problem 4 ( Disjoint-Separation-of-blue ) . Input: A set of red and blue points P in \mathbb{R}^{2} . Output: A minimum set \mathcal{T} of disjoint triangles containing all blue but no red points of P . Researchers addressed the problem of computing the minimum number of separators for a bichromatic point set. Canon and Cowen [ 4 ] first considered the problem of finding the minimum number of circles to separate a bichromatic point set in a general metric space. They proved that computing the minimum number of circles centered at the blue points to separate them from the red ones is NP-hard and presented a (\ln n+1) -factor approximation algorithm and devised a PTAS for the problem in \mathbb{R}^{d} . Bereg et al. [ 3 ] showed that computing the minimum number of axis-parallel rectangles to separate a bichromatic planar point set is NP-hard. In the same paper, they addressed the problem of separating objects by vertical or horizontal strips and presented a \mathcal{O}(r\log r+b\log b+\sqrt{rb}) -time exact algorithm where r and b are the numbers of red and blue points respectively. They also proved separation to be NP-hard if the separating objects are half-strips/squares and presented \mathcal{O}(1) -approximations. But separation and partition problems are not only interesting on the algorithmic side. Motivated by a question of Aharoni and Saks, Dumitrescu et al. [ 8 , 9 , 10 ] showed that every bichromatic set of n points can be partitioned into \lfloor\frac{n}{2}\rfloor+1 monochromatic subsets with disjoint convex hulls. This is not true if the subsets have a maximum size of 2. They give an algorithm to find a matching of size \frac{3}{7}n , but show that a monochromatic matching can in some cases only cover \frac{94}{95}n points. This is in contrast to the classic problem of Putnam that every bichromatic set of n blue and n red points admits a perfect matching of the red and the blue points ( [ 11 ] , for a proof of some generalization, see for instance [ 1 ] ). For both settings, the special case of a maximum size of a matching stabbed by a line with points on a circle has been of both long-term and recent interest under the name "necklace folding problem" [ 5 , 12 ] . cover both cover blue disjoint \geq\lfloor\frac{n}{2}\rfloor+1 ( Proposition B.1 ) \geq\lfloor\frac{n}{4}\rfloor+1 ( Proposition B.17 ) \leq\lfloor\frac{n}{2}\rfloor+1 ( Proposition B.3 ) \leq\lfloor\frac{2}{7}n\rfloor+1 ( Proposition B.9 ) overlap \geq\frac{3}{8}n-\Oh(1) ( Proposition B.17 ) \geq\lfloor\frac{n}{4}\rfloor+1 ( Proposition B.17 ) \leq\frac{13}{30}n+\Oh(1) ( Proposition B.5 ) \leq\frac{4}{15}n+\Oh(1) ( Proposition B.15 ) Table 1 : Summary of bounds on triangles separating bichromatic planar point sets of n points in total. We show that Problem 2 ( Overlap-Separation-of-blue ) . and Problem 4 ( Disjoint-Separation-of-blue ) . are NP-hard. Then we prove combinatorial bounds on the number of triangles required for the problems in the worst case for n points, see Table 1 . The paper is organized in the following manner. Section 2 describes the hardness of the problems by a polynomial time reduction from the Planar Monotone 3-SAT problem. Section 3 presents an overview of the combinatorial results. Finally, the paper is concluded in Section 4 . For detailed proofs we refer to the Appendix. 2 NP-hardness We present a polynomial-time reduction from the known NP-hard Planar Monotone (PM) 3-SAT [ 6 ] to the problems Problem 2 ( Overlap-Separation-of-blue ) . and Problem 4 ( Disjoint-Separation-of-blue ) . (Problems 2 and 4 ). PM 3-SAT is a special version of 3-SAT , where the usual boolean formula \phi is in conjunctive normal form, each clause contains 3 literals and all of them are either positive or negative. Moreover, there exists a planar embedding \Gamma_{\phi} of the incidence graph of \phi , in which the variables lie on the x -axis, the clauses with positive literals are above the x -axis and the clauses with negative literals are below the x -axis. Given a PM 3-SAT formula \phi , we construct a set of bichromatic points in the plane such that we can decide whether \phi is satisfiable based on the number of triangles in a minimum separator. The condition holds whether the triangles are allowed to overlap or not. Thus we simultaneously address the NP-hardness of both problems 2 and 4 . Figure 1 : The covering triangles of a variable gadget x_{i} . Robert: The white space between the dashed lines can be used for red points. Here we give an overview of the reduction without presenting the formal details. For the details, see Appendix A . Given a PM 3-SAT formula \phi with k variables x_{1},\ldots x_{k} and m clauses with a corresponding planar embedding \Gamma_{\phi} we will construct a bichromatic point set, such that all blue points can be covered with k+2m triangles, if and only if \phi is satisfiable. Let \varepsilon be small enough. First we describe how to replace the variable-vertices of \Gamma_{\phi} with variable gadgets. The variable x_{i} is represented by vertices in a square. Inside the square, place two covering triangles intersecting in a small triangle next to the point (2i,0) and place a blue point b_{i} in their intersection. For every clause c involving x_{i} , place a point p_{i}^{c} on a top or bottom segment close enough to the middle as in Figure 1 making sure that they are ordered according to the order of incidences of the clauses at x_{i} in \Gamma_{\phi} . Use the top segment if and only if c is positive. Now we replace the vertex associated to the positive clause c=x_{i}\vee x_{j}\vee x_{k},ik+2m=|\mathcal{T}| , there must be a triangle \triangle_{Q}\in\mathcal{T} that covers at least two points in Q and thus no other point in \bigcup_{Q^{\prime}\in\mathcal{T},Q^{\prime}\neq Q}{Q^{\prime}} . By repeating this argument for all Q^{\prime}\in\mathcal{T},Q^{\prime}\neq Q , we can see that no other triangle in \mathcal{T} apart from \triangle_{Q} covers any points in Q , thus Q is covered completely by \triangle_{Q} . This implies a unique one-to-one correspondence between \mathcal{Q} and \mathcal{T} . We construct a solution vector X\in\{\mathrm{True},\mathrm{False}\}^{k} of \phi in the following way: For every variable x_{i} let \triangle_{V_{i}}\in\mathcal{Q} be the unique element in \mathcal{Q} that covers V_{i} . If there exists a positive clause c_{j} containing the variable x_{i} , such that \triangle_{V_{i}} contains at least two points of the occurrence point cloud O_{j,i} , we set X[i]=\mathrm{True} . Note that in this case due to incompatibility, Q contains no point in a point cloud corresponding to a negative occurrence of c_{j} . If on the other hand the above condition is not fulfilled, we set X[i]=\mathrm{False} . Assume there is an unfulfilled clause c_{j}=(x_{a}\vee x_{b}\vee x_{c}) (or c_{j}=(\overline{x_{a}}\vee\overline{x_{b}}\vee\overline{x_{c}}) ). Since c_{j} is unfulfilled, none of the triangles \triangle_{V_{a}},\triangle_{V_{b}},\triangle_{V_{c}} covers two or more points of the occurrence point clouds O_{j,a},O_{j,b} or O_{j,c} , respectively. But due to pairwise incompatibility of O_{j,a},O_{j,b} and O_{j,c} , there exist three pairwise distinct triangles t_{a},t_{b} and t_{c}\in\mathcal{Q} that each cover at least two points of O_{j,a},O_{j,b} and O_{j,c} , respectively. But the only two point clouds in \mathcal{Q} that are compatible with O_{j,a},O_{j,b} or O_{j,c} are \triangle_{P_{j}^{\mathrm{left}}} and \triangle_{P_{j}^{\mathrm{right}}} , a contradiction. Thus, X is a valid truth-assignment for \phi , which concludes the proof. The only remaining piece to establish the NP-hardness of Problem 2 ( Overlap-Separation-of-blue ) . and Problem 4 ( Disjoint-Separation-of-blue ) . is to show that the construction of \mathcal{P} can be done in polynomial time. Lemma A.5 . Let \phi be a PM 3-SAT formula with k variables and m clauses. The point set \mathcal{P} together with their coordinates, constructed from \phi as described above, has polynomial size in k and m . Proof A.6 . We first show the total number of points we place is polynomial in terms of k and m . Each point cloud contains 2k+m+1 blue points, and we placed (k+5m) point clouds: a point cloud V_{i} for every variable x_{i} , and the five point clouds P_{j}^{\mathrm{left}} , P_{j}^{\mathrm{right}},O_{j,a} , O_{j,b} , O_{j,c} for every clause c_{j}=(x_{a}\vee x_{b}\vee x_{c}) or c_{j}=(\overline{x_{a}}\vee\overline{x_{b}}\vee\overline{x_{c}}) . The total number of blue points is thus m_{b}=(2k+m+1)\cdot(k+5m) . The number m_{r} of obstacles is upper bounded in \mathcal{O}(m_{b}^{3}) since for every triple of blue points we placed at most one obstacle. In order to show that the coordinates of the points are polynomial in terms of k and m as well, it suffices to show that the coordinates of the endpoints of covering triangles are polynomial in k and m . This clearly holds for the two covering triangles per variable gadget. The end-points of the triangle corresponding to clause gadgets are all constructed out of them by \mathcal{O}(k+m) steps, and in each of the steps the size of the coordinate in can only increase by a constant factor. Thus, the length of the binary representation can only increase by a constant additive term in each step, and the whole instance is of polynomial size. Therefore, the construction of the point set can be done in polynomial time. This implies the following theorem: Theorem A.7 . Problem 2 ( Overlap-Separation-of-blue ) . and Problem 4 ( Disjoint-Separation-of-blue ) . are NP-hard. Proof A.8 . Follows directly from A.3 and A.5 . We note that the precise complexity in which Problem 4 ( Disjoint-Separation-of-blue ) . is contained is unclear; however, for Problem 2 ( Overlap-Separation-of-blue ) . , this result can be strengthened. Theorem A.9 . Problem 2 ( Overlap-Separation-of-blue ) . is NP-complete. Proof A.10 . We know that Problem 2 ( Overlap-Separation-of-blue ) . is NP-hard from Theorem A.7 . We show that Problem 2 ( Overlap-Separation-of-blue ) . is also contained in NP. Let \mathcal{P} be a set of blue and red points. First, we argue that it suffices to consider only (possibly degenerate) triangles that have at least two points (we allow both red and blue) on each side segment. If we have a pseudo-solution consisting only of triangles of this type, the only thing that hinders it from being a real solution for the problem are that there are red points on the borders of the triangles. However, since the points lie in general position, we can always shrink this triangle such that it contains precisely the same blue points as before, but none of the red border points. The other way around, if we have any solution \mathcal{T} , we can transform every triangle, by taking each of the three sides and moving and/or rotating it individually until it hits 2 points while never losing any blue point in the set. In this manner, red points can appear only at the border of the triangle. With this categorization of a solution (or at least some type of pseudo-solution out of which we are guaranteed to be able to generate a solution), we construct all triangles that can be a part of such a solution in the following way: We compute the set \mathcal{L} of lines that contain precisely two points out of \mathcal{P} . Clearly, |\mathcal{L}|\in O(|\mathcal{P}|^{2}) We can then compute the set of candidate triangles (including the degenerate triangles) by taking all subsets of \mathcal{L} of size 3 or 1, and set them as the bounding lines of the respective triangle. This results in O(|\mathcal{L}|^{3}) = O(|\mathcal{P}|^{6}) triangles, out of which we can guess the right solution in nondeterministic polynomial time. Appendix B Detail results of Section 3 Proposition B.1 . Let k\geq 0 . Given a bichromatic point set on a closed convex curve in the plane such that 2k is the number of times two consecutive points on the curve have different colors, there is no set of k disjoint triangles containing all points such that no triangle contains points of both colors. Proof B.2 . We will prove the proposition by induction. Note that it holds for k=0 , because that means that only one color of points occurs and we must use a single, big enough triangle. Assume now k>0 . We start with a triangle to cover some of the points. Then this triangle cuts the curve into at most three pieces. We assume that there are exactly three pieces, where some pieces of the curve might not contain additional points. We can make those three pieces into closed convex curves again by routing a connection along the boundary of the cutting triangle. Let 2k_{1},2k_{2},2k_{3} be the number of color changes on these three parts. If there are no points, we set k_{i}=-1 since we clearly do not need additional triangles to cover those parts. By the convexity of the curve every triangle that covers some of the points can only cover points from one of the pieces, because otherwise it would intersect the cutting triangle. Therefore by induction we need at least k_{1}+1+k_{2}+1+k_{3}+1 triangles to cover the whole point set. We now know that any of the color changes either appeared on one of the three pieces or exactly one of the points was covered by the cutting triangle. In this case, the cutting triangle cuts the curve in between the two consecutive vertices of different colors. Since a triangle can cut a convex curve at most six times, we get: 2k\leq 2k_{1}+2k_{2}+2k_{3}+6\iff 1+k_{1}+1+k_{2}+1+k_{3}+1\geq k+1. However the latter is the total number of triangles we need, one for the original cutting triangle plus the number of triangles we still need to cover the three pieces, and it is at least k+1 . This concludes the proof. Proposition B.3 . Given a bichromatic planar n -point set, there are \lfloor\frac{n}{2}\rfloor+1 disjoint triangles within the convex hull of P containing all points such that no triangle contains points of both colors. Proof B.4 . In a first step, we show that it is sufficient to prove the statement for point sets with an odd number of points. Let P be a set with an even number n of points. Let x be a point from the convex hull of P and P^{\prime}=P\backslash\{x\} . Then P^{\prime} contains an odd number of points. Using the odd case, we can cover P^{\prime} with \frac{n}{2} triangles which stay in the convex hull of P^{\prime} . Since x is not in the convex hull of P^{\prime} , we can cover x itself with an additional triangle. Hence in total we can cover P with \frac{n}{2}+1 triangles. To show the odd case, we choose two points a,b with the same color at least one of which is from the convex hull of P . If we divide the point set P by the line ab , we obtain two smaller point sets. One of the point sets P_{o}(a,b) has an odd number of points. The other one has an even number. We count a and b to the part P_{e} with an even number of points. P_{e}(a,b) has the following property: • There are two points of the same color on the convex hull. As we show in the following, except for a few bad examples , those point sets can be covered with \frac{n}{2} triangles. The bad examples can be described as follows (in particular n=4,6 ): 1. Three points of the one color whose convex hull contains a point of the other color. 2. Three red and three blue points such that the convex hulls of the three points of each color contain a point of the other color. Moreover, for |P|=n\leq 12 , we checked these claims by computer using a SAT solver, see Appendix C . We prove the statements in the more general setting of pseudoconfiguration of points which are described via triple orientations of points. Moreover in order to study it with computer assistance we restrict to the cases where the triangles are spanned by at most 3 points of the point set. A detailed description of the SAT model is given in appendix C . 1. If n is odd, P can be covered with \frac{n+1}{2} triangles contained in \conv(P) . 2. If n is even and there are two consecutive points of the same color on the convex hull. Then P can be covered with \frac{n}{2} triangles contained in \conv(P) if P is not a bad example. For n>12 we show the two statements by induction. First, let P be a point set of n=2k bichromatic points with two consecutive points a and b on the convex hull with the same color, without loss of generality blue. Let P^{\prime}=P\setminus\{a,b\} . We say a point x\in P^{\prime} is visible from a and b if the triangle abx does not intersect the convex hull of the remaining points. If P^{\prime} contains two consecutive points of the same color on the convex hull, we cover a and b by a triangle. Since n>12 , P^{\prime} has at least 10 points and hence is not one of the bad examples. By induction, we can cover P^{\prime} by \frac{n}{2}-1 triangles. Hence P can be covered with \frac{n}{2} triangles. Moreover, if there is one point x on the convex hull of P^{\prime} which is blue and visible from a and b , the triangle abx does not intersect \conv(P^{\prime}\setminus\{x\}) . The number of remaining points is 2k-3 which is odd and smaller than 2k . By induction we can cover those points by \frac{2k-2}{2} triangles. Hence in total \frac{2k}{2}=\frac{n}{2} triangles cover P as claimed. Figure 5 : A visualization for the proof of Proposition B.3 . Hence all points x on the convex hull of P^{\prime} that are visible from a and b must be red. Since there is always at least one such point and those points form a consecutive part of the convex hull, which has no two consecutive points of the same color, there is exactly one visible point c from a and b which is red. For illustration refer to Figure 5 . Let d and e be the points next to c on the convex hull of P^{\prime} . Since no two consecutive points on the convex hull of P^{\prime} have the same color, d and e are both blue. Let \ell be the line spanned by c and d . Let f be the first of the not yet labeled points that is hit if we rotate it around c towards the remaining points of P^{\prime} . Since all points of P^{\prime} are on the same side of the line \ell and we rotated towards P^{\prime} all points of P^{\prime}\setminus\{d\} are on the same side of the line spanned by c and f . Since a and b are separated by the rotated line one of the two points is on the same side as P^{\prime}\setminus\{d\} . We assume without loss of generality b is on the same side. Hence c and f are two consecutive points on the convex hull of P\setminus\{a,d\} . If f is red, we can cover a and d by a triangle and proceed by induction on the point set P\setminus\{a,d\} which has two consecutive points on the convex hull of the same color. Hence by induction we can cover P with \frac{n}{2} triangles. Otherwise f is blue and the three blue points a,d,f span an empty triangle. This triangle does not intersect the convex hull of the points in P\setminus\{a,d,f\} . By induction for the odd case, we can cover those points with \frac{n-2}{2} triangles, which yields \frac{n}{2} triangles to cover P . This completes the proof for the even case. Now let P be a point set with an odd number n of bichromatic points. Without loss of generality there are more blue than red points. If there are two consecutive points of the same color on the convex hull, we can cover those with a triangle. The remaining point set can be covered with \frac{n-1}{2} triangles that do not overlap with this triangle by induction, thus we need at most \frac{n+1}{2} triangles to cover P . Thus there is a blue point a on the convex hull. Every pair (a,b) of blue points defines a line that splits the point set into two sets, one with an even number of points and one with an odd number of points. Note that every bad example has exactly 1 or exactly 3 blue points. Since the even side includes a and b it has exactly one further blue point if it is a bad example. Assume for contradiction that every pair (a,b) of blue points defines a bad even side. Fix some blue point b\neq a . If the odd side of (a,b) contains no blue points then we have 3 blue points and hence a point set with at most 5 points in total and the claim follows by the induction base. Thus the odd side contains a blue point. Rotate the line through a and b around a towards the odd side until the next blue point b^{\prime} is hit. The even side defined by (a,b^{\prime}) is again bad. The even side is not the one containing b though, since it would contain the even side of (a,b) and therefore another blue point. But then all blue points are contained either in the bad example defined by a,b or a,b^{\prime} . As these both only contain at most 3 blue points each, and they even share the point a , there are at most 5 blue points. As there are more blue than red points, we get n\leq 9 , all of which are cases we analysed by computer. It follows that we can find (a,b) such that the even side is not a bad example. Covering the resulting sides using induction yields a covering with the claimed number of triangles. Proposition B.5 . Given a bichromatic planar n -point set, there are \frac{13}{30}n+\Oh(1) triangles containing all points such that no triangle contains points of both colors. Proof B.6 . As we discuss in Appendix C , any point set of 15 blue and/or red points contains two vertex-disjoint monochromatic triangles. Thus we find at least 2\left\lfloor\frac{n}{15}\right\rfloor vertex-disjoint monochromatic triangles in our point set, scanning through the point set from left to right. These already cover 6\left\lfloor\frac{n}{15}\right\rfloor points. There are at most 9\left\lfloor\frac{n}{15}\right\rfloor+14 points left. We can cover them in pairs using at most an amount of \frac{9}{2}\left\lfloor\frac{n}{15}\right\rfloor+\frac{15}{2} additional triangles. This yields at most \frac{13}{30}n+\frac{15}{2} triangles in total. Lemma B.7 . Given a bichromatic point set in the plane consisting of b blue and r red points in general position, there is a set of at most \frac{2}{3}r+\frac{5}{3} disjoint triangles such that every blue point is contained in a triangle and no triangle contains a red point. Figure 6 : The two new generalized triangles for three new red points as in the proof of Lemma B.7 . Proof B.8 . Let a generalized triangle be an intersection of three half-planes such that every finite point set in it can be covered by a large enough triangle inside this intersection. Note that it is sufficient to show that the plane can be covered by at most \frac{2}{3}r+\frac{5}{3} generalized triangles such that all blue but none of the red points are contained in their disjoint interiors. We assume without loss of generality that all points have pairwise different x -coordinates. Denote the x -coordinates of the red points by x_{1}<\ldotsr-3 . If r^{\prime}=r , we use the half-plane x=x_{r} as the final generalized triangle to cover the plane with a total of \frac{2}{3}r+\frac{4}{3} generalized triangles. Otherwise we add two generalized triangles for the right side of the sweeping line separated by a line through the remaining ( \leq 2 ) red points. In total we cover the plane with at most \frac{2}{3}(r-1)+\frac{1}{3}+2=\frac{2}{3}r+\frac{5}{3} generalized triangles since r^{\prime}\leq r-1 . This completes the proof. Proposition B.9 . Given a bichromatic planar n -point set, there are \frac{2}{7}n+1 disjoint triangles containing all blue points such that no triangle contains a red point. Proof B.10 . Let b be the number of blue points and r the number of red points. If b\leq\frac{4}{7}n+1 , then we can cover all blue points in pairs from left to right, such that the resulting triangles are disjoint. This way we need at most \frac{b+1}{2}\leq\frac{2}{7}n+1 triangles. If r\leq\frac{3}{7}n-1 , we can apply Lemma B.7 to cover all blue points using at most \frac{2}{3}r\leq\frac{2}{7}n+1 triangles. Since b+r=n one of these two has to be the case, finishing the proof. Lemma B.11 . Given a bichromatic point set in the plane consisting of b blue and b-3t red points in general position, there is a set of t triangles with vertices at different blue points that do not contain a red point. Proof B.12 . We apply induction on t . If t=0 , we do not have anything to show. For the induction step let t\geq 1 and p be an arbitrary blue point. The other blue points have a fixed cyclic order around p such that at most one angle between two consecutive ones of them is larger than \pi . Thus out of the b-1 angles, at least b-2 can be used to define blue triangles of p and two consecutive points. The b-2 triangles constructed this way are interior disjoint. Since t\geq 1, the number of red points is at most b-3 . Hence at least one of the b-2 triangles does not contain red points. We now apply induction on the b-3 blue vertices that are not incident to this triangle and all of the b-3t=(b-3)-3(t-1) red points to obtain t-1 triangles with vertices at different blue points that do not contain a red point. Since the original triangle does not share a vertex with any of these by construction and does not contain red points either, the lemma follows. Corollary B.13 . Given a bichromatic point set in the plane consisting of b blue and b-3t red points in general position, where t\in\mathbb{N}_{0},t\leq\frac{b}{3} , there is a set of \lceil\frac{b-t}{2}\rceil triangles such that every blue point is contained in a triangle and no triangle contains a red point. Proof B.14 . By Lemma B.11 , there are t vertex-disjoint blue triangles covering at least 3 blue points each and not containing any red point. The remaining b-3t blue points can be covered in pairs as we did in Proposition B.5 . Using Iverson brackets [\cdot] the number of triangles used is t+\left\lceil\frac{b-3t}{2}\right\rceil=\frac{2t+b-3t}{2}+\frac{[2\nmid b-3t]}{2}=\frac{b-t}{2}+\frac{[{2\nmid b-t}]}{2}=\left\lceil\frac{b-t}{2}\right\rceil. Proposition B.15 . Given a bichromatic planar n -point set, there is a set of \frac{4}{15}n+\Oh(1) vertices, segments and triangles containing no red points and using all blue points as vertices exactly once. Proof B.16 . Let r and b be the number of red and blue points, respectively, and set x:=\frac{b-r}{3}\leq\frac{b}{3} . If there are more red points than blue points, then we can cover the blue points in pairs for an even better upper bound of \frac{1}{2}b+\Oh(1)\leq\frac{1}{4}(r+b)+\Oh(1) , so in the remaining case x\geq 0 . Note that n:=r+b=2b-3x is the total number of points. Taking the bounds from Lemma B.7 with t:=\lfloor x\rfloor and Corollary B.13 with r=b-3x , we get that the number of triangles required per point is upper bounded by \max_{x\in[0,\frac{b}{3}]}\min\left(\frac{\frac{2}{3}(b-3x)+\frac{5}{3}}{n},\frac{1}{n}\left\lceil\frac{b-\lfloor x\rfloor}{2}\right\rceil\right). This expression can be upper bounded by \max_{x\in[0,\frac{b}{3}]}\min\left(\frac{2x-\frac{2}{3}b-\frac{5}{3}}{3x-2b},\frac{x-b-2}{6x-4b}\right) via rearranging the terms and observing that \left\lceil\frac{b-\lfloor x\rfloor}{2}\right\rceil\leq\frac{b-\lfloor x\rfloor+1}{2}\leq\frac{b-x+2}{2}. Regarding b as a constant, we can see that both expressions in the minimum are monotone in x for x\in[0,\frac{b}{3}] . The first is monotonically decreasing while the second is monotonically increasing. This implies that the worst case is attained for the unique value of x making both expressions equal. Setting them equal yields x=\frac{1}{9}(b-16) . Therefore the number of triangles required per point is upper bounded by \frac{\frac{1}{9}(b-16)-b-2}{\frac{6}{9}(b-16)-4b+4}=\frac{4b+17}{15b+30}. This completes the proof. Proposition B.17 . There are bichromatic planar n -point sets such that there is no set of \lfloor\frac{n}{4}\rfloor triangles containing all blue points and no set of \frac{3}{8}n+\Oh(1) triangles containing all points such that no triangle contains points of both colors. Proof B.18 . Consider the following construction. Place blue points p_{1},\ldots,p_{b} on a circle in that order and draw the complete graph on them with straight lines. Let e be the edge between p_{b} and p_{1} . Each point p_{i} is incident to b-2 cells. If i\neq 1,b exactly one of these cells is inside the triangle defined by e and p_{i} . Place a red point r_{i} inside each such cell. This way we place b-2 red points. See Figure 7 for illustration. Figure 7 : Illustrations for the proof of Proposition B.17 . From left to right, (a): The construction. (b): A red triangle covering 4 red points. (c): The lines \ell_{1},\ell_{2} and \ell_{3} as in the proof. B_{1} consists of the star-shaped blue points, B_{2} of the diamond-shaped blue points and B_{3} of the square-shaped blue points. Claim . There is no blue triangle containing three blue points. Proof of the claim: We see that it is enough to consider triangles with blue points as corners as any triangle containing three blue points contains one of these in its interior. Let abc be a triangle where a,b and c are blue points. Let a and c be the points to the left and to the right of the edge e along the circle. We see that b is not a point of e , i.e. we have placed a red point p next to b . The line bp intersects e and hence also intersects the line ac . Therefore p is inside abc . Claim . There is no red triangle containing more than four red points. Proof of the claim: Consider the three lines \ell_{1},\ell_{2} and \ell_{3} defined by the edges of a red triangle. For every blue point at least one of these lines separates the triangle and this point. Let B_{1} be the set of blue points separated by \ell_{1} and from among the rest of the points the points of B_{2} are separated by \ell_{2} . Let B_{3} be the remaining points which are thus separated from the triangle by \ell_{3} . In particular, |B_{1}|+|B_{2}|+|B_{3}|=b . Note that since we cut them off using a line, all three of the B_{i} are consecutive points along the convex hull of blue points, so their convex hulls do not intersect each other or the triangle. But to avoid any blue triangles in B_{i} we need at least |B_{i}|-2 red points inside of its convex hull, see Lemma B.11 . Hence there are at least |B_{1}|-2+|B_{2}|-2+|B_{3}|-2=b-6 red points that are not contained in the triangle. This implies that at most 4 red points are covered. It is easy to see that indeed 4 red points can be covered by a triangle not containing a blue point. With these two claims it is now clear that we need at least \frac{1}{4}(b-2) triangles for the red points and at least \frac{1}{2}b triangles for the blue points. As n=2b-2 we need k+1 triangles for the blue points if and only if b\geq 2k+1\Leftrightarrow{n\geq 4k} and up to the constant \frac{3}{4}b\approx\frac{3}{8}n triangles in total. Appendix C Computational Aspects For a point set in general position which we study in this paper, three points a,b,c are either oriented clockwise or counterclockwise. This gives rise to so-called triple orientations, which can be encoded as Boolean variables. Using these variables we encode questions about sets of a fixed number of points as a Boolean satisfiability instance, which we then study using a SAT solver. Not every assignment of triple orientations can be represented by a point set and deciding realizability is in fact a computationally hard problem [ 13 ] . We can however add clauses to ensure that certain necessary conditions are fulfilled. More specifically, we consider the search space of so-called pseudoconfiguration of points , which contain all point sets. Besides using the combinatorial structure of triangle orientations, we assume without loss of generality that the points have distinct x -coordinate, which allows us to order them from left to right with increasing x -coordinate. The triangle orientation of those points are encoded in the combinatorial setting of rank 3 signotopes. This structure turns out to be more efficient in the encoding since we have to add less constraints. We use the encoding from [ 16 ] , which comes with one Boolean variable for each triple of points to indicate whether the triple is positively or negatively oriented. Clauses ensure that solutions of the Boolean formula correspond to signotopes. In addition, we need to assign a color to each point. For this we introduce variables and clauses which ensure that each point has exactly one color. For the considered problem, we look for triangles covering some points of the same color and not containing points of the other color. In order to formulate it as a CNF, we only consider triangles which are spanned by points of the actual point set. Three points give a proper triangle. However, if only two points are contained in a triangle we always find a sufficiently small triangle covering the straight-line segment between those two points without containing any other points of the point set. Similarly this holds for triangles consisting of only one point. Moreover, the encoding comes with auxiliary variables to indicate whether a pair of edges cross, and auxiliary variables to indicate whether a triangle contains points in its interior. Since those properties are characterized by the triple orientations, these auxiliary variables are synchronized with the orientation variables via clauses. C.1 Full cover In the proof of proposition B.3 we study a bichromatic point set P and consider the problem whether we can cover this point set with k monochromatic triangles such that each triangle is spanned by at most 3 points of P with the same color and does not contain any points of the other color. To simplify this problem with computer investigation, we consider triangles which do not contain any other points of P . Assume towards a contradiction that a bichromatic point set P=\{p_{1},\ldots,p_{n}\} exists which cannot be covered by k triangles. We can assume without loss of generality that the points p_{1},\ldots,p_{n} have increasing x -coordinate, and therefore the induced triple-orientations form a rank 3 signotope on [n] as discussed above. To the general setting above which encodes bichromatic point sets, we add clauses to ensure that no partition [n]=\bigcup_{i=1}^{k}I_{j} with |I_{j}|\in\{1,2,3\} is valid. In particular, for each such partition (I_{1},\ldots,I_{k}) , we add a clause to ensure that there is a pair I_{a},I_{b} which is not disjoint or one I_{a} does not span a monochromatic empty triangle. If two I_{a},I_{b} parts are not disjoint, then their convex hulls have an intersection, which we can encode using the intersection auxiliary variables. In the other case if one I_{a} does not span a monochromatic empty triangle, then either two points of I_{a} have the same color or the triangle contains a point of [n] . Those conditions can be encoded using the variables encoding the colors of the points or the empty triangle auxiliary variables. Even though the number of partitions [n]=\bigcup_{i=1}^{k}I_{j} grows exponentially in n , the instances for up to n=15 are of reasonable size and can be performed on a laptop. For larger n , where more RAM was required, we used a computing cluster. Moreover, we used the symmetry breaking (as explained in [ 16 ] ) to reduce the search space: without loss of generality the points s_{2},\ldots,s_{n} appear in this cyclic order around s_{1} (which lies on the convex hull). C.2 Two vertex-disjoint triangles In proposition B.5 , we want to find a lower bound on the number of triangles with which every bichromatic point set in general position in the plane can be covered. As shown in [ 16 ] , every set of 17 points contains a pair of area-disjoint empty pentagons [ 16 ] . By pigeon hole principle every such empty pentagon contains a monochromatic empty triangle. Hence 17 is an upper bound on the number of points required to find two vertex-disjoint monochromatic empty triangles. Partitioning the point set with a sweeping line in parts of 17 points shows that 6 out of those 17 points can be covered with two triangles. The remaining points can be covered with monochromatic matching edges. Using the SAT framework, we show that every set of 15 points contains a pair of vertex-disjoint triangles, which clearly improves the bound as discussed in the proof of proposition B.5 . Since there exists a set of 14 points with no pair of vertex-disjoint triangles, the bound is optimal. For this problem we look for a bichromatic point set which avoids two vertex-disjoint triangles spanned by exactly three points of the same color. Again we start with the framework explained above and model this problem by adding a clause that for each pair of monochromatic triangles they intersect or one of them is not empty. Again this can be done with the auxiliary variables explained above. Additionally we checked for further improvement, by allowing that the vertex disjoint monochromatic triangles contain points of the same color. Using our SAT framework this does not yield an improvement as there are bichromatic point sets with 14 points without two such monochromatic triangles but each set of 15 points contains two such triangles. In order to get an improvement we also tried to find three vertex disjoint monchromatic triangles. Using our program we found a pseudopoint configuration on 20 elements with no three disjoint triangles. The computations took about 10 CPU hours. Since we add clauses for each set of three triangles, the instances grow fast and we did not manage to start larger instances.