Bichromatic Quadrangulations with Steiner Points

Abstract. Let P be a k colored point set in general position, k ≥ 2. A family of quadrilaterals with disjoint interiors Q1,..., Qm is called a quadrangulation of P if V (Q1) ∪...∪V (Qm) = P, the edges of all Qi join points with different colors, and Q1 ∪... ∪ Qm = Conv(P). In general it is easy to see that not all k-colored point sets admit a quadrangulation; when they do, we call them quadrangulatable. For a point set to be quadrangulatable it must satisfy that its convex hull Conv(P) has an even number of points and that consecutive vertices of Conv(P) receive different colors. This will be assumed from now on. In this paper we study the following type of questions: Let P be a k-colored point set. How many Steiner points in the interior of Conv(P) do we need to add to P to make it quadrangulatable? When k = 2, we usually call P a bichromatic point set, and its color classes are usually denoted by R and B, i.e. the red and blue elements of P. In this paper we prove that any bichromatic � point � set P = R ∪B where |R | = |B | = n can be n−1 made quadrangulatable by adding at most 3 + �n � m 2 + 1 Steiner points and that 3 Steiner points are occasionally necessary. To prove the latter, we also show that the convex hull of any monochromatic point set P of n elements can be always partitioned into a set S = {S1,... � �, St} n−1 of star-shaped polygons with disjoint interiors, where V (S1)∪ · · ·∪V (St) = P, and t ≤ 3 +1. For n = 3k this bound is tight. Finally we prove that there are 3-colored point sets that cannot be completed to 3-quadrangulatable point sets. Key words. Triangulations, quadrangulations, bicolored point sets, Steiner points. 1