A Cellular Triangle Containing a Specified Point

Graphs and Combinatorics (1999) 15 : 239±247

Graphs and Combinatorics ( Springer-Verlag 1999

A Cellular Triangle Containing a Specified Point Shin-ichi Tokunaga College of Liberal Arts and Sciences, Tokyo Medical and Dental University, 2-8-30 Kohnodai, Ichikawa, Chiba 272-0827, Japan e-mail: [email protected]

Abstract. Let P be a set of ®nite points in the plane in general position, and let x be a point which is not contained in any of the lines passing through at least two points of P. A line l is said to be a k-bisector if both of the two closed half-planes determined   by l contain jPj -bisector and at least k points of P. We show that if any line passing through x is a 3 does not contain two or more points of P, then there exist three points p1 ; p2 ; p3 of P such that D p1 p2 p3 contains x and does not containpoints  of P in its interior, and such that each jPj -bisector. of the lines passing through two of them is a 3

1. Introduction For a subset V of the Euclidian plane R 2 , let conv…V † denote the convex hull of V. Let P be a ®nite set of points in R 2 . For a point x A R 2 , the depth of x with respect to P, denoted by dep…P; x†, is the minimal number of points of P conained in a closed half-plane determined by a line passing through x  jPj . For three non-colinear points x; y; z A R 2 , denote by clealy dep…P; x† U 2 H ‡ …x; y; z† (resp. H ÿ …x; y; z†) the open half-plane which is determined by the line passing through y; z, and contains (resp. misses) x. Further let P…x; y; z† :ˆ P V H ‡ …y; z; x† V H ‡ …z; x; y† (see Fig. 1). A generalized version of Perles' rooted tree embedding problem (see [1]) is partially solved in [2] by making use of a property of ®nite point sets in the plane. Further in [2], the auther made the following conjecture, which seems contribute to the complete solution of the problem (the statement is slightly modi®ed): Conjecture 1. Suppose that n ˆ jPj V 3, and let k1 ; k2 ; k3 be integers such that 0 U nÿ2 and k1 ‡ k2 ‡ k3 ˆ n ÿ 3. Let x be a point of R 2 ÿ P, and 2 suppose that P U fxg is in general position and dep…P; x† V k3 ‡ 1. Then there exist three non-collinear points p1 ; p2 ; p3 of P such that P V conv…f p1 ; p2 ; p3 g† ˆ k1 U k2 U k3 U

240

S. Tokunaga

Fig. 1

f p1 ; p2 ; p3 g and the following inequalities hold: jP… p1 ; p2 ; p3 †j U k1 U jP V H ÿ … p1 ; p2 ; p3 †j; jP… p2 ; p3 ; p1 †j U k2 U jP V H ÿ … p2 ; p3 ; p1 †j; jP… p3 ; p1 ; p2 †j U k3 U jP V H ÿ … p3 ; p1 ; p2 †j; As a partial solution of the above conjecture, we show the following. Theorem 1. Let P, k1 ; k2 ; k3 , and x be as in Conjecture 1. Then there exist three non-collinear points p1 ; p2 ; p3 of P such that x A conv…fp1 ; p2 ; p3 g†, P V conv…fp1 ; p2 ; p3 g† ˆ f p1 ; p2 ; p3 g, and the following three inequalities hold: jP V H ÿ …p1 ; p2 ; p3 †j V k1 ; ÿ

…1†

jP V H …p2 ; p3 ; p1 †j V k2 ;

…2†

jP V H ÿ …p3 ; p1 ; p2 †j V k3 :

…3†

2

If a subset S of R contains no points of P in its interior, S is said to be vacuum. Further, following Kupitz [3], we call a convex polygon D cellular if D is vacuum and all vertices of D are points of P. Kupitz also introduced the notation of a kbisector, which is a line l such that both of the two closed halfplanes determined by l contain at least k points of P. With this terminology, we can state a special case of Theorem 1 as follows: Corollary 1. Let P be a set of n …V3† points in general position l n m in the plane, and let 2 -bisector and does not x A R ÿ P. Suppose that each line passing through x is a 3

A Cellular Triangle Containing a Speci®ed Point

241

contain two or more points of P. Then there l n mexists a cellular triangle D of P containing x such that each edge of D is on a -bisector. 3 2. Proof We ®rst settle a special case of Theorem 1: Claim 1. Let P, k1 ; k2 ; k3 ; x be as in Theorem 1. Suppose that there exist q1 ; q2 ; q3 A P such that Dq1 q2 q3 contains x; Dxq1 q2 , Dxq1 q3 are both vacuum, jP…x; q1 ; q2 †j U k3 and jP…x; q1 ; q3 †j U k2 . Then the conclusion of Theorem 1 holds. Proof. For two distinct points a, b in the plane, let ab denote the open line segment connecting a and b. We ®x a point y A R 2 so that xy contains q1 . Take p20 A P as follows: if jP…q1 ; q2 ; y†j V k3 , set p20 ˆ q2 ; otherwise take p20 A P V H ‡ …q2 ; q1 ; x† so that jP…q1 ; p20 ; y†j ˆ k3 (note that there exists such p20 because jP V H ‡ …q2 ; q1 ; x†j V dep…P; x† V k3 ‡ 1). Similarly, set p30 ˆ q3 if jP…q1 ; q3 ; y†j V k2 , and otherwise, take p30 A P V H ‡ …q3 ; q1 ; x† so that jP…q1 ; p30 ; y†j ˆ k2 . Also let ( ÿ H …q1 ; x; qi † if pi0 ˆ qi Hi :ˆ H ‡ …x; q1 ; pi0 † otherwise for i ˆ 2; 3. Then P V H2 V H3 contains at lest k1 points of P:

…4†

Set p1 ˆ q1 , and take p2 ; p3 so that pi A H ‡ …pi0 ; x; q1 † V ……P V H2 V H3 † U fp20 ; p30 g† for i ˆ 2; 3, and H ‡ … p; p2 ; p3 † V conv……P V H2 V H3 † U f p20 ; p30 g† ˆ q (i.e., p1 p3 is an edge of conv……P V H1 V H3 † U f p20 ; p30 g† facing p1 ; see Fig. 2). Then since jP…q1 ; p20 ; y†j V k3 and jP…q1 ; p30 ; y†j V k2 , (2) and (3) or Theorem 3 clearly hold. Moreover, since …P V H2 V H3 † U fp20 ; p30 g is contained in H ÿ …p1 ; p2 ; p3 † U r f p2 ; p3 g, (1) follows from (4). Next we prove another special case, which is the most essential part:  Claim 2. The conclusion of Theorem 3 holds when k1 ˆ   nÿ3 . k3 ˆ 3

   nÿ5 nÿ4 , k2 ˆ , 3 3

Proof. Let D be the family of all cellular polygons D containing x, and let D 0 be the family of D 0 A D such that for any two adjacent edges r1 r2 ; r2 r3 of D 0 …r1 ; r2 ; r3 A P†, jP…x; r1 ; r2 † U P…x; r2 ; r3 †j V k1 holds. Note that D 0 is non-empty set since any cellular triangle containing x belongs to D 0 by the assumption that

242

S. Tokunaga

Fig. 2

dep…P; x† V k3 ‡ 1. An edge pq of D A D is said to be a crowded edge if jP…x; p; q†j > k1 , and a deserted edge if jP…x; p; q†j U k1 . Since n ˆ jPj U 3k1 ‡ 5, for each D A D the number of crowded edges of D is at most two:

…5†

Furthermore, if D 0 A D 0 , then D 0 has at most ®ve edges. We henceforth assume that no three points of P satisfy the assumption of Claim 2;

…6†

in particular, each D A D has no two adjacent deserted edges r1 r2 ; r2 r3 such that Dr1 r2 r3 contains x:

…7†

For an edge pq of D A D, we say pq is a good edge (resp. very good edge) if jP V H ÿ …x; p; q†j V k1 (resp. V k3 ). It su½ces to show that there exists a cellular triangle containing x two of whose edges are very good and the other one is good.

A Cellular Triangle Containing a Speci®ed Point

243

Note that since k3 U k1 ‡ 1, an edge of D A D is very good if it is a crowded edge. 0 Let Ed …D† be the P set of all deserted edges of D A D. We henceforth ®x D0 A D so that f …D0 † :ˆ pq A Ed …D0 † €pxq is maximum. Case 1. D0 is a triangle (see Fig. 3a). Let r1 ; r2 ; r3 A P be the vertices of D0 . In view of (5) and (7), D0 has two crowded edges, which are at the same time very good edges, and a deserted edge. By symmetry, we may assume that r1 r2 and r2 r3 are crowded edges, and r3 r1 is a deserted edge. We have only to show that r3 r1 is a good edge. We ®rst prove P…r1 ; r2 ; r3 † ˆ q. Suppose that P…r1 ; r2 ; r3 † 0 q. Then we can take s A P…r1 ; r2 ; r3 † so that the quadragon D1 ˆ r1 r2 sr3 is cellular. Applying (5) to D1 , we see that r2 s or sr3 must be a deserted edge. If D1 A D 0 , this contradicts the maximality of f …D0 †. Thus D1 B D 0 , which means that sr3 is a deserted edge and jP…x; s; r3 † U P…x; r3 ; r1 †j U k1 ÿ 1 holds. Applying (7) to D1 , we also see that Dr1 r3 s does not contain x, and hence Dr1 r2 s is a member of D 0 with a deserted edge sr1 , which again contradicts the maximality of f …D0 †. Consequently, P…r1 ; r2 ; r3 † ˆ q. Let l be the line passing through x and parallel to r1 r2 and H be the closed half-plane which is bounded by l and contains r3 . Then …P V H† ÿ fr3 g J P V H ÿ …x; r3 ; r1 † and hence jP V H ÿ …x; r3 ; r1 †j V jP V Hj ÿ 1 V dep…P; x† ÿ 1 V k3 ; i.e., r3 r1 is a (very) good edge. Case 2. D0 is a quadrangle By (7), D0 has at least one crowded edge. In view of (5), there are two subcases to be considered. Subcase 2.1. D0 has one crowded edge and three deserted edges (see Fig. 3b). Let r1 r2 be the crowded edge and let r2 r3 , r3 r4 , r4 r1 be the deserted edges. Again by (7), Dr1 r3 r4 and Dr2 r3 r4 does not contain x, which immediately implies that Dr1 r2 r3 and Dr1 r2 r4 contain x. Since r1 r2 , r1 r3 , r2 r4 are very good edges (of Dr1 r2 r3 or Dr1 r2 r4 ), it su½ces to show that r2 r3 or r4 r1 is a good edge. If P…r3 ; r2 ; r4 † V P…r4 ; r1 ; r3 † 0 q, then there exists s A P…r3 ; r2 ; r4 † V P…r4 ; r1 ; r3 † such that sr2 r3 r4 r1 is a cellular pentagon and, arguing as in Case 1, we see that one of sr2 r3 r4 r1 , sr2 r3 r4 or sr3 r4 r1 yields a contradiction to the maximality of f …D0 †. Thus P…r3 ; r2 ; r4 † V P…r4 ; r1 ; r3 † ˆ q. Therefore, P H P…x; r3 ; r4 † U H ÿ …x; r2 ; r3 † U H ÿ …x; r4 ; r1 † U fr1 ; r2 ; r3 ; r4 g. Since r3 r4 is a deserted edge, jP V H ÿ …x; r2 ; r3 †j V k1 or jP V H ÿ …x; r4 ; r1 †j V k1 holds, which settles this subcase. Subcase 2.2. D0 has two crowded edges and two deserted edges (see Fig. 3c). By the de®nition of D 0 , the two deserted edges cannot be adjacent. Let r1 r2 and r3 r4 be the deserted edges, and let r2 r3 and r4 r1 be the crowded edges. Without loss of generality, we may assume Dr1 r2 r3 contains x. If jP V H ÿ …x; r1 ; r2 †j V k3 , Dr1 r2 r3 clearly has three very good edges. Thus we may assume jP V H ÿ …x; r1 ; r2 †j U k3 ÿ 1. On the other hand, again as in Case 1, we see that H ‡ …x; r1 ; r2 † V

244

S. Tokunaga

Fig. 3

H ‡ …x; r3 ; r4 † is vacuum, i.e., fr1 ; r2 ; r3 ; r4 g U …P V H ÿ …x; r1 ; r2 †† U …P V H ÿ …x; r3 ; r4 †† ˆ P:

…8†

Thus, considering the line passing through x and parallel to r3 r4 , we obtain jP V H ÿ …x; r1 ; r2 †j  dep…P; x† ÿ 2 V k3 ÿ 1: Since jP V H ÿ …x; r1 ; r2 †j U k3 ÿ 1, this implies

…9†

A Cellular Triangle Containing a Speci®ed Point

245

Fig. 4

jP V H ÿ …x; r1 ; r2 †j ˆ dep…P; x† ÿ 2 ˆ k3 ÿ 1:

…10†

Let s1 ; s2 be the two points of P which are adjacent to x in the boundary of conv…fx; r3 ; r4 g U …P V H ÿ …x; r3 ; r4 †††. We choose our notation so that s1 A H ‡ …r3 ; x; r4 † and s2 A H ‡ …r4 ; x; r3 † (see Fig. 4). Then, (8) implies that H ‡ …x; r1 ; r2 † V …H ÿ …s1 ; x; s2 † U H ÿ …s2 ; x; s1 †† is vacuum:

…11†

Further, considering the lines passing through x; s1 and x; s2 , (8) together with the ®rst equality in (10) also implies that fr1 ; r2 g U …P V H ÿ …x; r1 ; r2 †† H H ÿ …s1 ; x; s2 † V H ÿ …s2 ; x; s1 †:

…12†

Note that (12) implies s1 ; s2 A H ‡ …x; r1 ; r2 †:

…13†

Now by (12), Dr1 s1 s2 (and Dr2 s1 s2 ) contains x, and hence by (11) and (13), Dxr1 s1 and Dxr1 s2 are both vacuum. Moreover, it follows from (11), (13) and the second equality in (10) that jP…x; r1 ; s1 †j U j…P V H ÿ …x; r1 ; r2 †† U fr2 gj ˆ k3 and jP…x; r1 ; s2 †j U jP V H ÿ …x; r1 ; r2 †j ˆ k3 ÿ 1 U k2 : Hence s1 ; s2 and r1 satisfy the assumption of Claim 2 with q1 ˆ r1 , q2 ˆ s1 , q3 ˆ s2 . This contradicts (6), and this contradiction completes the discussion for Subcase 2.2.

246

S. Tokunaga

Case 3. D0 is a pentagon (see Fig. 3d). Let ri A P …1 U i U 5† be the vertices of D0 and let ri ri‡1 …1 U i U 5† be the edges of D0 (here indices are reduced modulo 5). In this case, all edges of D0 are deserted edges, so f …D0 † ˆ 2p. By (7), each Dri ri‡1 ri‡2 does not contain x, and hence each Dri ri‡1 ri‡3 contains x and has two very good edges ri‡1 ri‡3 and ri‡3 ri . Therefore we have only to ®nd an edge ri ri‡1 of D0 satisfying jP V H ÿ …x; ri ; ri‡1 †j V k1 . Retake r2 ; r3 ; r4 ; r5 so that € r2 xr3 ‡ € r4 xr5 is minimum. Suppose that P V H ‡ …x; r1 ; r2 † V H ‡ …x; r3 ; r4 † V H ÿ …x; r2 ; r3 † 0 q. Then there exists s A P V H ‡ …x; r1 ; r2 † V H ‡ …x; r3 ; r4 † V H ÿ …x; r2 ; r3 † such that r1 r2 sr3 r4 r5 is a cellular hexagon. Again by (7), we see that Dr1 sr4 contains x, i.e., Dr1 sr4 A D 0 . Thus as in Case 1, Dr1 sr4 has two crowded edges and one deserted edge. Since r4 r1 is a crowded edge, one of r1 s and sr4 is deserted, and the other one is crowded. We may assume that r1 s is deserted and sr4 is crowded. Then the pentagon r1 sr3 r4 r5 yields a contradiction to the minimality of € r2 xr3 ‡ € r4 xr5 . Thus P V H ‡ …x; r1 ; r2 † V H ‡ …x; r3 ; r4 † V H ÿ …x; r2 ; r3 † ˆ q; and we similarly get P V H ‡ …x; r3 ; r4 † V H ‡ …x; r5 ; r1 † V H ÿ …x; r4 ; r5 † ˆ q: This implies that H ‡ …x; r1 ; r2 † V H ‡ …x; r3 ; r4 † V H ‡ …x; r5 ; r1 † is vacuum, i.e., P H fr1 ; r2 ; r3 ; r4 ; r5 g U H ÿ …x; r1 ; r2 † U H ÿ …x; r3 ; r4 † U H ÿ …x; r5 ; r1 †: Thus one of H ÿ …x; r1 ; r2 †, H ÿ …x; r3 ; r4 †, H ÿ …x; r5 ; r1 † contains at least k1 points of P, which completes the proof of Claim 2. r Finally we prove the general case. Proof of Theorem 1. We may again assume that the assumption of Claim 1 does not hold, i.e., (6) holds. By  Claim 2, there exists a cellular triangle D p1 p2 p3 such nÿ5 for each i ˆ 1; 2; 3 (here indices are reduced that jP V H ÿ …x; pi ; pi‡1 †j V 3     nÿ3 nÿ5 ˆ , jP V H ÿ …x; pi ; pi‡1 †j V k1 holds for modulo 3). Since k1 U 3 3 each i ˆ 1; 2; 3. If jP…x; p3 ; p1 †j U k2 , it follows from (6) that jP…x; p1 ; p2 †j > k3 and jP…x; p2 ; p3 †j > k3 , which immediately implies that the conclusion of Theorem 1 holds. Similarly the case where jP…x; p1 ; p2 †j U k2 and the case where jP…x; p3 ; p1 †j U k2 are settled by relabelling p1 ; p2 ; p3 . Consequently, we are left with the case where jP…x; pi ; pi‡1 †j > k2 …i ˆ 1; 2; 3†

…14†

holds. Retake p1 ; p2 ; p3 so that (14) holds and € p2 x p3 is minimum. We argue as in Case 1 of the proof of Claim 2. Suppose that P… p1 ; p2 ; p3 † 0 q. Then we can take s A P… p1 ; p2 ; p3 † so that p1 p2 s p3 is a cellular quadrangle. Then D p1 p2 s and D p1 p3 s are cellular, and one of them contains x. Without loss of generality, we may assume D p1 p2 s contains x. Note that since k1 U k2 U k3 and jP…x; p1 ; p2 †j ‡ jP…x; p2 ; p3 †j ‡ jP…x; p3 ; p1 †j ˆ jPj ÿ 3 ˆ k1 ‡ k2 ‡ k3 ;

A Cellular Triangle Containing a Speci®ed Point

247

it follows from (14) that jP…x; pi ; pi‡1 †j < k3 …i ˆ 1; 2; 3†. In particular, jP…x; p1 ; p2 †j < k3 . Thus by (6), jP…x; p2 ; s†j > k2 . Since jP…x; s; p1 †j > jP…x; p3 ; p1 †j > k2 , D p1 p2 s yields a contradiction to the minimality of €p2 x p3 . Hence P…p1 ; p2 ; p3 † ˆ q. Now arguing exactly as in Case 1 of the proof of Claim 2, we see that p1 p2 is ``very good'', i.e., jP V H ÿ …x; p1 ; p2 †j V k3 , and hence the conclusion of Theorem 1 holds. rr Acknowledgments. I would like to thank the referees and Yoshimi Egawa for valuable comments.

References 1. Ikebe, Y., Tamura, A., Tokunaga, S., Perles, M.: The rooted tree embedding problem into points on the plane, Discrete Comput. Geom. 11, 51±63 (1994) 2. Tokunaga, S.: On a straight-line embedding problem of graphs, Discrete Mathematics 150, 371±378 (1996) 3. Kupitz, Y.S.: Separation of a ®nite set in R d by spanned hyperplanes, Combinatorica 13(3) 249±258

Received: October 16, 1995 Revised: October 16, 1996