Matching points with disks with a common intersection

Matching points with disks with a common intersection Clemens Huemera, Pablo Pérez-Lanterob, Carlos Searaa, Rodrigo I. Silveiraa aDepartament de Matemàtiques, Universitat Politècnica de Catalunya, Spain bDepartamento de Matemática y Ciencia de la Computación, Universidad de Santiago, Chile Abstract We consider matchings with diametral disks between two sets of points Rand B. More precisely, for each pair of matched points p∈Rand q∈B, we consider the disk through pand qwith the smallest diameter. We prove that for any Rand Bsuch that |R|=|B|, there exists a perfect matching such that the diametral disks of the matched point pairs have a common intersection. In fact, our result is stronger, and shows that a maximum weight perfect matching has this property. 1. Introduction We consider two sets of n≥2points in the plane, Rand B, that are assumed to be disjoint. We call the points in Rred, and those in Bblue. A well-known family of problems involving red and blue points is that of matching points with (pairwise disjoint) geometric objects. The goal is to find pairs of points such that each pair is associated with a geometric object that covers both points of the pair, and all associated objects are pairwise disjoint. In each pair the two points are restricted to be of different colors, or in each pair the two points are restricted to be of the same color. This class of problems is well studied in discrete and computational geometry, starting from the classic result that nred points and nblue points can always be perfectly matched with n pairwise non-crossing segments, where each segment connects a red point with a blue point [1]. The study has been continued in plenty of directions, for both the monochromatic and bichromatic versions, by using pairwise disjoint segments [2, 3], rectangles and squares [4, 5, 6, 7], and more general geometric objects [8]. More formally, for R={p1, . . . , pn}and B={q1, . . . , qn}, a matching of R∪Bis a partition of R∪Binto npairs such that each pair consists of a red and a blue point. A point p∈Rand a point q∈Bare matched if and only if the pair (p, q)is in the matching. We use pq to denote the segment connecting pand q, and |pq|to denote its length. The diametral disk of pq, denoted Dpq, is the disk with diameter equal to |pq|that is centered at the midpoint of pq, while Cpq is the corresponding circle. For a matching M, we use DMto denote the set of disks associated with the matching, that is: DM={Dpq |(p, q)∈ M}. Email addresses: [email protected] (Clemens Huemer), [email protected] (Pablo Pérez-Lantero), [email protected] (Carlos Seara), [email protected] (Rodrigo I. Silveira) 1 Figure 1: Example for a set of n= 4 red and blue points, showing a matching and the associated disks, which have a common intersection. In this paper, we prove that for any Rand Bas above, there always exists a matching Msuch that all disks in DMhave a common intersection (see Figure 1). More precisely, we show that any maximum matching satisfies this property. A matching Mof R∪Bis maximum if it maximizes the sum of the squared distances between the matched points, that is, it maximizes P(p,q)∈M |pq|2. Observe that our result goes in the direction opposite to that of known results on matching red and blue points: Our goal is that all matching objects have a common intersection, whereas in previous work (e.g., [2, 3, 4, 5, 6, 7, 8], and the references in [8]) it is required that all matching objects are pairwise disjoint. Moreover, in order for the problem to make sense, the object used for the matching is important. Segments—arguably the simplest geometric object defined by two points—do not work. That is, when matching points of different colors with segments, it is not always possible to guarantee that all matching segments are pairwise intersecting (e.g., consider two red and two blue points not in convex position). This also happens when matching with axis-aligned rectangles, where for any two matched points the associated rectangle is the one with minimum-area that contains both points. For these reasons, we focus on matching with disks. The choice of diametral disks comes from the need of bounding the size of the disks. Otherwise, if disks can be arbitrarily large, the result becomes trivially true. Furthermore, diametral disks are a natural choice for disks that must be defined by two points. A D I Figure 2: Example for a set of n= 3 red, white, and green points, showing a partition into three-colored triangles, which have a common intersection. Our result is also motivated from Tverberg’s theorem [9], which states that any (d+1)(r−1)+1 points in Rdcan be partitioned into rsubsets such that the convex hulls of the subsets have a point in common. A colored version of this theorem for points in the plane was proved in [10], implying that any set of nred, nwhite, and ngreen points in the plane can be partitioned into ntriangles, with one vertex from each color, such that the triangles have a point in common. See Figure 2. Many extensions and related results are known, see for instance [11, 12, 13, 14]. Here we consider diametral disks instead of convex hulls. Hence, our result can be put into the context of Tverberg type theorems. Other related results, albeit for different problems, include those in [15, 16, 17, 18, 19]. Outline. We begin by introducing some additional notation. After that, we consider a maximum matching Mof R∪B, and prove in Section 2 that any pair of disks in DMintersect. Finally, in Section 3, we prove that all disks in DMmust intersect. Notation. For a point p, let x(p)and y(p)denote the x- and y-coordinates of p, respectively. Given three different points p,q, and r, let `(p, q)denote the line containing both pand q,∆pqr 2 p1 q1 q2 p2 x=d1 4 x=d2 4 (a) p1 q1 (b) ˜q2 ˜q1 Cp1q1 Cp2q2 q2 p2 Figure 3: (a) Illustration of Lemma 1. (b) Illustration of Lemma 2. the triangle with vertex set {p, q, r},∠pqr the angle at qin the triangle ∆pqr. Finally, we will say that a set of points is in general position if no three points of the set are collinear. 2. Any two disks in DMintersect We begin by showing in this section that in a maximum matching M, any pair of disks in DMintersect. To that end, we first prove the following auxiliary result that concerns only four points. This result will also be the key for proving our main technical result, Lemma 6. Lemma 1. Let p1, p2∈Rand q1, q2∈Bsuch that {(p1, q1),(p2, q2)}is a maximum matching for {p1, p2, q1, q2}. Suppose further that y(p1) = y(p2), and x(p1)< x(p2). Then, x(q2)≤x(q1). Proof. Assume w.l.o.g. that p1= (−1,0) and p2= (1,0). Refer to Figure 3(a). Given a constant c, the points r= (x, y)that satisfy |rp1|2−|rp2|2=care those such that (x+1)2+y2−(x−1)2−y2=c, which is equivalent to 4x=c. Then, the locus of such points is the vertical line x=c/4. Since {(p1, q1),(p2, q2)}is a maximum matching, we have that |p1q1|2+|p2q2|2≥ |p1q2|2+|p2q1|2⇐⇒ |p1q1|2− |p2q1|2≥ |p1q2|2− |p2q2|2. Let d1=|p1q1|2− |p2q1|2and d2=|p1q2|2− |p2q2|2. Note that the vertical line through q1is the line x=d1/4, thus x(q1) = d1/4, and analogously, x(q2) = d2/4. Since d2≤d1, we have x(q2)≤x(q1). Now we can prove that in a maximum matching for four points, the two disks intersect. Lemma 2. Let p1, p2∈Rand q1, q2∈Bsuch that {(p1, q1),(p2, q2)}is a maximum matching for {p1, p2, q1, q2}. Then, Dp1q1∩Dp2q26=∅. Proof. Assume w.l.o.g. that y(p1) = y(p2)and x(p1)< x(p2). Refer to Figure 3(b). Let ˜q1and ˜q2be the orthogonal projections of q1and q2on `(p1, p2), respectively. By Thales’ theorem, ˜q1lies on Cp1q1, which implies p1˜q1=Dp1q1∩`(p1, p2). Similarly, ˜q2lies on Cp2q2, and p2˜q2=Dp2q2∩`(p1, p2). By Lemma 1, x(q2)≤x(q1), which implies that segments p1˜q1and p2˜q2have a point in common. Hence, Dp1q1∩Dp2q26=∅. 3 A B C B0 A0 C0 hBC hAB hCA Figure 4: Illustration of Lemma 3. The lemma states that for any three points in general position A, B, C, one can define three points A0, B0, C0based on certain perpendicular lines, such that the associated diametral disks (shown red) intersect at one point. It remains to extend the previous result to npoints. To that end, observe that in any maximum matching Mof R∪B, where |R|=|B| ≥ 2,{(p1, q1),(p2, q2)}is a maximum matching of {p1, p2, q1, q2}for every pair (p1, q1),(p2, q2)∈ M. That is, any two pairs of a maximum matching form also a maximum matching for the four points involved. Therefore, applying Lemma 2 we can conclude that in any maximum matching Mthe disks DMare pairwise intersecting. 3. All disks in DMintersect The main goal of this section is to generalize the result in Lemma 2 from four to six points. That is, we will consider sets of three disks from a maximum matching, and will show in Lemma 6 that we can always shrink the disks until finding a point in common. Then Helly’s theorem will imply our main result. However, this will require considerably more effort and the help of several geometric observations. The next three lemmas describe three different geometric situations at which we will arrive in the proof of Lemma 6. The first lemma is illustrated in Figure 4. Lemma 3. Let A,B, and Cbe three points in the plane in general position. Let hAB,hBC , and hCA be three lines that are perpendicular to `(A, B),`(B, C), and `(C, A), respectively. Let the points A0=hAB ∩hCA,B0=hAB ∩hBC , and C0=hBC ∩hCA. Then, the three circles CAA0,CBB0, and CCC0intersect at one point. Proof. Without loss of generality assume that A= (a, 0),B= (b, 0), and C= (0, c), for some a < 0, and b, c > 0. Observe that triangles ∆ABC and ∆A0B0C0are similar, so that ∆A0B0C0is 4 obtained from ∆ABC by a rotation of π/2radians, a scaling of factor λ, for some λ > 0, and finally a translation by some vector (α, β)∈R2. Assume that the rotation is counter-clockwise (the clockwise case is analogous). Then we have A0=λ·(0, a)+(α, β) = (α, λa +β),B0=λ·(0, b)+(α, β) = (α, λb +β), and C0=λ·(−c, 0) + (α, β)=(−λc +α, β). The points (x, y)of CAA0are those such that the scalar product between vectors (x, y)−A= (x−a, y)and (x, y)−A0= (x−α, y −λa −β)equals zero. That is, (x−a)(x−α) + y(y−λa −β) = 0.(1) Similarly, the points (x, y)of CBB0satisfy that the scalar product between (x, y)−B= (x−b, y) and (x, y)−B0= (x−α, y −λb −β)equals zero. That is, (x−b)(x−α) + y(y−λb −β)=0.(2) One solution to the system formed by equations (1) and (2) is the point (α, 0) = hAB ∩`(A, B), which is one of the intersection points between CAA0and CBB0. The other intersection point (considering multiplicity) can be found as follows. Subtracting (2) from (1): (b−a)(x−α) + y(λ(b−a)) = 0 x=−λy +α. (3) Substituting equation (3) in equation (1), we obtain (−λy +α−a)(−λy) + y(y−λa −β)=0 y(λ2y+y−λα −β)=0 y=λα +β 1 + λ2. Then, x=−λλα +β 1 + λ2+α=−λ2α−λβ +α+λ2α 1 + λ2=−λβ +α 1 + λ2.(4) The points (x, y)of CCC0satisfy that the scalar product between vectors (x, y)−C= (x, y −c) and (x, y)−C0= (x+λc −α, y −β)equals zero. That is, x(x+λc −α)+(y−c)(y−β)=0.(5) To show the lemma it suffices to prove that (x, y)=(−λβ+α 1+λ2,λα+β 1+λ2)satisfies equation (5). x(x+λc −α) = −λβ +α 1 + λ2−λβ +α 1 + λ2+λc −α =−λ−λβ +α 1 + λ2λα +β−c−λ2c 1 + λ2 (y−c)(y−β) = λα +β 1 + λ2−cλα +β 1 + λ2−β =λλα +β−c−λ2c 1 + λ2−λβ +α 1 + λ2 =−x(x+λc −α). 5 Therefore, (x, y) = (−λβ+α 1+λ2,λα+β 1+λ2)satisfies equation (5) and is common to CAA0,CBB0, and CCC0. We continue with the following lemma that describes a situation on four points. Refer to Figure 5. Lemma 4. Let A,B,P, and Rbe four points in the plane such that `(A, B)is horizontal, Bis to the right of A,Pbelongs to `(A, B), and Ris above `(A, B). Let C1be the circle through the points A,P, and R, and C2be a circle through Band P. If C1and C2are tangent, let O=P, otherwise let Obe the intersection point different from Pbetween C1and C2. Then, if C2does not enclose R, the points Oand Bare in the same side of `(A, R). Proof. Consider the case where Pis to the right of A(see Figure 5a). Make a circle inversion at A(with any radius), and let B0,P0,R0,O0,C0 1, and C0 2denote the images of B,P,R,O,C1, and C2, respectively (see Figure 5b). Note that C0 2is the circle through P0,B0, and O0, and C0 1is the line `(P0, R0)because C1goes through the center of the inversion A. Observe that P0and B0are in the same half-plane bounded by `(A, R0) = `(A, R). Since C2does not enclose A, the center of the inversion, C2does not enclose Rif and only if C0 2does not enclose R0. Then, C0 2does not enclose R0, which implies that O0lies on the line segment R0P0. This ensures that O0and B0, also Oand B, are in the same side of `(A, R). Consider now the case where Pis to the left of A(see Figure 5c). Make again a circle inversion at A, in which C0 1is the line `(P0, R0)(see Figure 5d). Since C2encloses the center Aof the inversion, C2does not enclose Rif and only if C0 2encloses R0. Then, C0 2encloses R0, which implies that R0belongs to the segment P0O0, and also that P0and O0are separated by `(A, R0) = `(A, R). This guarantees that O0and B0, also Oand B, are in the same half-plane bounded by `(A, R). Finally, we need one more technical lemma, illustrated in Figure 6. Lemma 5. Let `be a line, and R, C ∈`two points. Let hbe a half-line with apex point Hsuch that the supporting line of his perpendicular to `at point R. Let δbe the half-plane bounded by `such that δ∩his a half-line. Then, for any two points X, Y ∈hwith |XH|≤|Y H|, we have DXC ∩δ⊆DY C ∩δ. Proof. Consider the more general case in which hand `intersect at R. The other case where h and `do not intersect can be proved similarly. We analyze three cases, depending on where the points Xand Ylie on h. i) Let X, Y ∈HR be two points satisfying |XH| ≤ |Y H|(see Figure 6a). Then, we have ∠RXC ≤∠RY C. For any two points X0∈ CXC and Y0∈ CY C in the interior of δ, we have ∠RX0C=π−∠RXC and ∠RY 0C=π−∠RY C. This implies ∠RY 0C≤∠RX0C, and hence DXC ∩δ⊆DY C ∩δ. ii) Let X, Y ∈(h\HR)∪ {R}be two points satisfying |XH|≤|Y H|(see Figure 6b). For any two points X0∈ CXC and Y0∈ CY C in the interior of δ, we have ∠RY 0C=∠RY C ≤∠RXC = ∠RX0C. This implies DXC ∩δ⊆DY C ∩δ. iii) Finally, if X∈HR and Y∈(h\HR)∪{R}, from the first case we have DXC ∩δ⊆DRC ∩δ, and from the second one DRC ∩δ⊆DY C ∩δ. Hence, DXC ∩δ⊆DY C ∩δ, and the lemma is proved. We have now all the tools to prove the main lemma in this work. 6 A B R P O C1 C2 (a) A B0 R0 P0 O0 C0 1 C0 2 (b) A B R P O C1 C2 (c) A B0 R0 P0 O0 C0 1 C0 2 (d) Figure 5: Illustration of Lemma 4. Lemma 6. Let p1, p2, p3∈Rand q1, q2, q3∈Bsuch that {(p1, q1),(p2, q2),(p3, q3)}is a maximum matching for {p1, q1, p2, q2, p3, q3}. Then, the disks Dp1q1,Dp2q2, and Dp3q3have a point in common. Proof. The idea is to reduce the disks Dp1q1,Dp2q2, and Dp3q3as much as possible so that each of the new three disks is contained in its corresponding original disk, and the new disks still have a point in common that is easier to find than for the original disks. We begin by observing that a maximum matching for three pairs of points must also be maximum for any subset of two pairs, thus the implications of Lemma 1 must hold for any two pairs that we take. We will shrink the three diametral disks as much as possible, while maintaining the conditions of Lemma 1. Formally, for every ε1∈[0,|p1q1|],ε2∈[0,|p2q2|], and ε3∈[0,|p3q3|], let q1(ε1)∈ p1q1,q2(ε2)∈p2q2, and q3(ε3)∈p3q3be the points such that |q1q1(ε1)|=ε1,|q2q2(ε2)|=ε2, and |q3q3(ε3)|=ε3. Let (˜ε1,˜ε2,˜ε3)be a maximal point of the set [0,|p1q1|]×[0,|p2q2|]×[0,|p3q3|]such that the conditions of Lemma 1 are satisfied pairwise, that is, the following three statements hold: (1) in the direction from p1to p2,q2(˜ε2)is not to the right of q1( ˜ε1); (2) in the direction from p2to p3,q3(˜ε3)is not to the right of q2( ˜ε2); (3) in the direction from p3to p1,q1(˜ε1)is not to the right of q3(˜ε3). 7 H X Y R C ` δ h (a) H X Y R C ` δ h (b) Figure 6: Illustration of Lemma 5. The point (˜ε1,˜ε2,˜ε3)is maximal if there does not exist any other point (ε0 1, ε0 2, ε0 3)∈[0,|p1q1|]× [0,|p2q2|]×[0,|p3q3|]such that ˜ε1≤ε0 1,˜ε2≤ε0 2,˜ε3≤ε0 3, and the above three conditions are also satisfied by using (ε0 1, ε0 2, ε0 3)instead of (˜ε1,˜ε2,˜ε3). Let ˜p1=q1(˜ε1),˜p2=q2(˜ε2), and ˜p3=q3(˜ε3). Note that Dp1˜p1⊆Dp1q1,Dp2˜p2⊆Dp2q2, and Dp3˜p3⊆Dp3q3. We prove now that Dp1˜p1,Dp2˜p2, and Dp3˜p3have a point in common, which implies the lemma. If p1,p2, and p3belong to the same line `(assuming w.l.o.g. that they appear in this order in `), then the points ˜p1,˜p2, and ˜p3belong to the same line `0perpendicular to `. By Thales’ theorem, the point `∩`0is common to Dp1˜p1,Dp2˜p2, and Dp3˜p3. Hence, assume from now on that p1,p2, and p3are in general position. Then, there are two cases to consider: Case 1:˜pi=pifor some i∈ {1,2,3}. Assume w.l.o.g. ˜p3=p3(see Figure 7a). Then Dp3˜p3consists of a single point, p3. Let s1and s2be the orthogonal projections of ˜p1on `(p1, p3), and ˜p2on `(p2, p3), respectively. From the third condition above, we have that in the direction from p3to p1, point ˜p1is not to the right of ˜p3. Thus, we have p3∈p1s1. Similarly, since in the direction from p2to p3, point ˜p3is not to the right of ˜p2, we have p3∈p2s2. By Thales’ theorem p1s1⊂Dp1˜p1and p2s2⊂Dp2˜p2, hence p3= ˜p3is common to Dp1˜p1,Dp2˜p2, and Dp3˜p3. Case 2:˜p16=p1,˜p26=p2, and ˜p36=p3. By construction of ˜p1,˜p2, and ˜p3, at least two pairs of lines among (`(p1, p2), `(˜p1,˜p2)),(`(p2, p3), `(˜p2,˜p3)), and (`(p3, p1), `(˜p3,˜p1)) form perpendicular lines. Note that this last statement follows from the fact that (˜ε1,˜ε2,˜ε3)is taken as a maximal point. That is, at least two segments among p1q1(ε1),p2q2(ε2), and p3q3(ε3)cannot be shortened by decreasing their corresponding values of ε1,ε2, and ε3, so that statements (1-3) are still satisfied. For example, the extreme cases of statement (1) are when lines `(p1, p2)and `(q1(ε1), q2(ε2)) are perpendicular. Assume w.l.o.g. that `(˜p1,˜p2)is perpendicular to `(p1, p2), and that `(˜p3,˜p1)is perpendicular to `(p3, p1)(see Figure 7b). Let s12 =`(p1, p2)∩`(˜p1,˜p2),s13 =`(p1, p3)∩`(˜p1,˜p3), and let s∗be the point of `(˜p1,˜p3)such that `(s∗,˜p2)is perpendicular to `(p2, p3). By Thales’ theorem, s12, s13 ∈ Cp1˜p1,s12 ∈ Cp2˜p2, and s13 ∈ Cp3˜p3. If Cp1˜p1and Cp2˜p2are tangent at s12, let O=s12, otherwise let Obe the intersection point other than s12 between Cp1˜p1and Cp2˜p2. By Lemma 3, we have that O=Cp1˜p1∩ Cp2˜p2∩ Cp3s∗. 8 p1 p2 p3= ˜p3 ˜p1 ˜p2 s1 s2 (a) p1 p2 p3 ˜p2 ˜p1 ˜p3 s12 O s13 h s∗ (b) Figure 7: Illustration of the two cases considered in the proof of Lemma 6: (a) ˜p3=p3, (b) ˜p36=p3. If Cp2˜p2contains s13, then we are done, since s13 is also common to Dp1˜p1and Dp3˜p3. Hence, assume Cp2˜p2does not contain s13. Under this assumption, by Lemma 4 (used with points A= p1,B=p2,P=s12, and R=s13), Oand p2are in the same half-plane Hbounded by `(p1, p3). Since ˜p3is not to the right of `(s∗,˜p2)in the direction from p2to p3, we have that ˜p3is on the half-line h⊂`(s∗,˜p1)with apex s∗and such that h∩ H is a half-line. By Lemma 5, Dp3s∗∩ H ⊆ Dp3˜p3∩ H, and hence O∈Dp3˜p3, which implies that Ois common to Dp1˜p1,Dp2˜p2, and Dp3˜p3. Theorem 1. Given a set Rof n≥2red points and a set Bof nblue points, in any maximum matching of Rand B, the disks have a common intersection. Proof. Let M={(p1, q1),(p2, q2),...,(pn, qn)}be a maximum matching of R∪B. If n= 2, then Dp1q1∩Dp2q26=∅by Lemma 2, implying the theorem. Otherwise, if n≥3, for every different i, j, k ∈ {1,2, . . . , n}the matching {(pi, qi),(pj, qj),(pk, qk)}must be maximum for {pi, qi, pj, qj, pk, qk}. Then, by Lemma 6, Dpiqi∩Dpjqj∩Dpk,qk6=∅. The result follows by Helly’s theorem. 4. Matching points with other shapes We finish by observing that the fact that disks, and not other arbitrary shapes, are used to match the pairs of points is important. As mentioned before, it is clear that simpler shapes such as line segments do not have the property of giving always a common intersection. Furthermore, we observe that replacing circles by somewhat similar shapes, such as hexagons or decagons, in general does not preserve the property. We can adapt the definition of diametral disk to regular hexagons or decagons as follows. Define the diametral hexagon (resp. decagon) of a pair of points as the smallest-area regular hexagon (resp. decagon) that contains both points on its boundary. In Fig. 8 we show a simple construction that consists of four points on the vertices of a square, alternating colors. The point set in the construction has two different perfect matchings, which 9