Convex Polyhedra in R3 Spanning Congruent Triangles

Convex polyhedra in R3 spanning -(n4=3 ) congruent triangles. Abstract We construct n-vertex convex polyhedra with the property stated in the title In this note we construct, for every ¯xed triangle T , a n-vertex convex polyhedron determining -(n4=3 ) triangles congruent to T among its triplets. Even with the convexity assumption dropped, this was only known when T is an isosceles right triangle (see [2] and [4]). With respect to the upper bound Brass [2] proved that n points in R3 span at most O(n7=4+" ) triangles congruent to T and very recently Agarwal and Sharir [1] improved this and obtained the current best bound of O(n5=3+" ). There are no better bounds that take advantage of the convexity restriction. We say that a ¯nite subset of R3 is in convex position if it is the vertex set of a convex polyhedron. CH(K) will denote the convex hull of K and @K the boundary of K. We prove a slighthly stronger statement. Let U be a quadrilateral with perpendicular diagonals. Assume u1 = (d1 ; 0; 0); u2 = (0; 0; d2 ); u3 = (¡d3 ; 0; 0); and u4 = (0; 0; ¡d4 ) with di > 0 are the vertices of U and o = (0; 0; 0) is the intersection of its diagonals. For any ¯nite set P µ R3 let F (U; P ) be the number of quadruplets in P congruent to U. Let © ª F3conv (U; n) = max F (U; P ) : P µ R3 ; P in convex position, jP j = n , since any triangle T can be completed to such a quadrilateral U (by re°ecting upon the largest side), it is enough to prove that Theorem 1 F3conv (U; n) = -(n4=3 ) The proof of the Theorem will be based on two lemmas. For every 0 < ® < ¼2 and 1 · i · 4 de¯ne the following arcs of circle Arci (®) = fv = (x; y; z) : y = 0; kvk = di ; j]voui j < ®g ³ ³S ´´ S 4 Lemma 1 There is ® > 0 so that 4i=1 Arci (®) µ @ CH Arc (®) : i i=1 Proof. Suppose d1 · d2 , let ®1;2 = 12 arcsin(d1 =d2 ). Let a and b be points in the plane y = 0 de¯ned by kak = d1 ,kbk = d2 , and ]u1 oa = ]bou2 = ®1;2 . By construction ]aob = ¼ ¼ 2 ¡ 2®1;2 , thus cos(]aob) = sin(2®1;2 ) = d1 =d2 , and then ]oab = 2 . This proves that Arc1 (®1;2 ) [Arc2 (®1;2 ) µ @ (CH (Arc1 (®1;2 ) [ Arc2 (®1;2 ))). Clearly any value smaller than ®1;2 would work for the pair (d1 ; d2 ), therefore by picking ® · 21 arcsin(min1·i;j·4 di =dj ) the result follows. 1 © ª Let e1 = (1; 0; 0), e2 = (0; 0; 1), e3 = (¡1; 0; 0), e4 = (0; 0; ¡1), and S = v 2 R3 : kvk = 1 . The next lemma without the additional property (ii) was ¯rst proved in [4] by Erd}os et al. Lemma 2 For every " > 0 and n 2 N there are n-sets Q1 ; Q2 ; Q3 ; Q4 µ S with the following properties (i) There are cn4=3 quadruplets (q1 ; q2 ; q3 ; q4 ) with qi 2 Qi and q1 q2 q3 q4 a square of diameter 2. (ii) ]qi oei < " for every qi 2 Qi , 1 · i · 4. Proof. Erd} os (see [3]) constructed an n-element set P in the plane and a set of n lines L p such that the number of incidences among them is at least cn4=3 (The set P consists of a n£ p n grid, and L includes the n lines with more points in P ). We can assume that all lines in ªL © have slope smaller than ¡1 and also that P µ (x; y; ¡1) 2 R3 : x 2 (m; m + 1); y 2 (0; 1) . For every p = (xp ; yp ; ¡1) 2 P let qp1 and qp3 be the points obtained as the intersection of S with the line po, i.e., if p = (x; y; ¡1) then qp1 = ¡qp3 = kpk¡1 (xp ; yp ; ¡1). Also for every l 2 L with equation z = ¡1; Al x + Bl y = Cl , (Cl > 0 and A2l + Bl2 + Cl2 = 1) consider the plane ¼l through o which contains l. Let ql2 and ql4 be the points obtained as the intersection of S with the line through o perpendicular to ¼l , i.e., ql2 = ¡ql4 = (Al ; Bl ; Cl ). For i = 1; 3 let Qi = fqpi : p 2 P g and Qi+1 = fqli+1 : l 2 Lg. Assume p 2 l, p by construction, ql2 and ql4 are at distance 2 from every point in the circle ¼l \ S, in particular from qp1 and qp3 . Since qp1 ; qp3 and ql2 ; ql4 are antipodes on S we conclude that S qp1 ql2 qp3 ql4 is a square of diagonal 2. Therefore the number of such squares in 4i=1 Qi is at least cn4=3 . Now, to prove property (ii) we show that for all p 2 P; l 2 L, and i = 1; 3 ° ° ° ° lim °qpi ¡ ei ° = lim °qli+1 ¡ ei+1 ° = 0: m!1 m!1 By symmetry we only prove this equality for i = 1: If p 2 P then xp 2 (m; m + 1) and yp < 1, thus ° 1 ° 2m °qp ¡ e1 °2 = 2 ¡ 2xp < 2 ¡ p ¡! 0 when m ! 1: kpk 2 + (m + 1)2 If l 2 L then, in the plane z = ¡1, l has slope ¡Al =Bl < ¡1 and it intersects the solid square (m; m + 1) £ (0; 1). Thus 0 < Cl =Bl and m < Cl =Al , but since Cl > 0 we get 0 < Bl < Al and Al < Cl =m. Hence µ ¶ 2 2 2 2 2 2 2 2+m 1 = Al + Bl + Cl < 2Al + Cl < Cl ; m2 therefore ° 2 ° °ql ¡ e2 °2 = 2 ¡ 2Cl < 2 ¡ p 2m ¡! 0 when m ! 1. 2 + m2 2 S4 ³ Proof ³S of Theorem. ´´ By Lemma 1 there is 0 < ® < ¼=2 so that i=1 Arci (®) µ 4 @ CH . Let " = ® and apply Lemma 2. For 1 · i · 4 de¯ne Pi = i=1 Arci (®) S fdi qi : qi 2 Qi g. We P ¤ := 4i=1 Pi gives the desired bound. ³S claim that ´ 4 0 00 Let K = CH i=1 Arci (®) . Construct K and K as the solids of revolution obtained from K by revolving around the x-axis and the z-axis respectively. Let K ¤ = K 0 \K 00 , clearly © ª K ¤ is a convex set, and for 1 · i · 4 the sets Capi (®) = v 2 R3 : kvk = di ; j]voui j < ® are caps of sphere which satisfy that Capi (®) µ K 0 \ K 00 \ (@K 0 [ @K 00 ) = @(K 0 \ K 00 ) = @K ¤ : ¤ ¤ Now, by property (ii) ]pi oui < ® for every pi 2 PS i , thus Pi µ Capi (®) and P µ @K . ¤ 4 Finally, since any supporting plane of K intersects i=1 Capi (®) in at most one point, we conclude that P ¤ is in convex position; and clearly d1 q1 ; d2 q2 ; d3 q3 ; d4 q4 is congruent to U whenever q1 q2 q3 q4 is a square of diameter 2. Hence F (U; 4n) ¸ F (U; P ¤ ) ¸ cn4=3 as we wanted to prove. 3