Note on the number of obtuse angles in point sets

XV Spanish Meeting on Computational Geometry, June 26-28, 2013 Note on the number of obtuse angles in point sets Ruy Fabila-Monroy ∗ 1 , Clemens Huemer † 2 , and Eulàlia Tramuns ‡ 2 1 Departamento de Matemáticas, Cinvestav-IPN 2 Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, BarcelonaTech Abstract In 1979 Conway, Croft, Erd®s and Guy proved that every set S of n points in general position in the plane determines at least n3 18 −O(n2) obtuse angles and also showed the upper bound 2n3 27 −O(n2) on the minimum number of obtuse angles among all sets S . We prove that every set S of n points in convex position determines at least 2n3 27 −o(n3) obtuse angles, hence matching the upper bound (up to sub-cubic terms) in this case. Also on the other side, for point sets with low rectilinear crossing number, the lower bound on the minimum number of obtuse angles is improved. Introduction A point set S in the plane is in general position if no three points of the set lie on a common straight line. Throughout, all considered point sets S will be in general position in the plane and |S|=n. An angle abc at b determined by three points {a, b, c} of S is obtuse if it is greater than π 2 . Prominent problems and results on obtuse and acute angles in point sets can be found in [4]. Here we are interested in the number of obtuse angles determined by point sets S . Conway et al. [3] proved that the minimum number of obtuse angles among all sets S is between n3 18 −O(n2) and 2n3 27 −O(n2) . In this note we prove that point sets S in convex position determine at least 2n3 27 −o(n3) obtuse angles. Interestingly, this matches (up to subcubic terms) the upper bound example from [3]. We conjecture that 2n3 27 is indeed the right order of magnitude for the minimum number of obtuse angles. Point sets in convex position are characterized as the point sets that maximize the rectilinear crossing number . The rectilinear crossing number cr(S) of a point set S equals the number of convex quadrilaterals with ∗ Email: [email protected]vestav.edu.mx. Partially supported by Conacyt of Mexico, Grant 153984. † Email: [email protected]c.edu. Partially supported by projects MEC MTM2012-30951 and Gen. Cat. DGR 2009SGR1040 and ESF EUROCORES programme EuroGIGA, CRP ComPoSe: grant EUI-EURC-2011-4306, for Spain. ‡ Email: etramu[email protected]c.edu. Partially supported by MTM2011-28800-C02-01 from Spanish MEC. ij i a b c Figure 1: Alternately skipping i and j points in the polygonal path for class (i, j) . vertices in S . Hence, an upper bound of n 4 on the rectilinear crossing number is obvious. As for point sets with low crossing number, the current best lower bound is 277 729 n 4+Θ(n3) [2] and there are point sets S that only have cr(S)=0.380488n 4+ Θ(n3) [1]. We show that point sets S whose crossing number is not too large, at most 2 3n 4 , have more than n3 18 obtuse angles. Proofs Theorem 1 Every set S of n points in convex and general position in the plane determines at least 2n3 27 − o(n3) obtuse angles. Proof. First we consider the case when n is a prime number; the case when n is not a prime number will be treated at the end of the proof. We label the points of S from 0 to n−1 in counter-clockwise order. For three points a, b, c ∈S in counter-clockwise order, we say that the angle abc at point b is of class (i, j) if the open halfplane bounded by the line through points a and b , and not containing point c contains i points of S , and if the open halfplane bounded by the line through points b and c , and not containing point a contains j points of S ; see Figure 1. (Then ab is an i -edge and bc is a j -edge.) Hence each angle dened by S belongs to some class (i, j), where 0≤i+j≤n−3. For i, j xed, i6=j , we consider the polygon P that starts at point 0 , visits points of S in counter-clockwise order, alternately skipping i points and j points of S , until it returns to point 0 the second time. Three steps of 89 Note on the number of obtuse angles in point sets such a polygonal path of P are shown in Figure 1. Note that the polygon P is self-intersecting and can visit vertices more than once. • Claim: Each angle of class (i, j) and each angle of class (j, i) is encountered exactly once in P . We modify P to obtain a new polygon P0 by pairing two consecutive steps of P which skip i points and j points respectively; that is, we now move from a point m to point m+i+j+ 2 mod n. Since n is a prime number, each non-zero element of the additive group Zn is a generator of the group; in particular also i+j+ 2. This implies that P0 returns to the starting point 0 after it visited each point of S\{0} exactly once. We now retrieve the original polygon P by splitting the paired steps into steps skipping alternately i points and j points. It follows that each point of S is visited twice in P , and each angle of class (i, j) and each angle of class (j, i) is encountered exactly once in P . • Claim: The rotation number [5] of the polygon P is i+j+ 2. The rotation number measures how many times the polygon turns around. Note that the underlying point set is in convex position and all steps are done in counter-clockwise order. The polygon visits each vertex m twice; from a point m the polygonal path continues once to point m+i+ 1 mod n , and once to point m+j+ 1 mod n ; in total the path advances i+j+ 2 points from m . Hence, summing over all n vertices, we count (i+j+ 2)n steps between consecutive points of the point set in counter-clockwise order. n steps between consecutive points describe one full turn. Thus the rotation number is i+j+ 2 . • Claim: At least 2n−3(i+j+ 2) angles of the 2n angles of classes (i, j) and (j, i) encountered in P are obtuse. For the sake of contradiction, suppose that P contains less than 2n−3(i+j+2) obtuse angles. Then, P contains more than 3(i+j+ 2) acute or right angles. By an averaging argument, at least one of the i+j+ 2 full turns of the polygon contains more than three acute or right angles. But this is not possible, unless P contains four right angles forming a 4 -cycle contradicting n being a prime number. Hence, each pair of classes (i, j) and (j, i) of angles, with i6=j , contains at least 2n−3(i+j+2) obtuse angles. Summing over all possible values i, j we thus get the lower bound on the number of obtuse angles in S 1 2 b2n 3−2c X i=0 b2n 3−2−ic X j=0,j6=i 2n−3(i+j+2) = 2n3 27 −O(n2). It remains to consider the case when n is not a prime number. In this case it suces to only count the number of obtuse angles in a subset S0 of S consisting of np points, where np is the largest prime number smaller than n . Since np> n−o(n) , see e.g. [6], we get the lower bound on the number of obtuse angles in S 2(n−o(n))3 27 −O(n2) = 2n3 27 −o(n3).  Lemma 2 Every set S of n points in general position in the plane with rectilinear crossing number cr(S) determines at least n3 12 −cr(S) n−3−O(n2) obtuse angles. Proof. We rst remark that the number of right angles formed by S is negligible for our purpose. In fact, it is enough to observe that no edge spanned by S is incident to more than two right angles, due to the general position assumption. Hence we upper bound the number of right angles by 2n 2. Each 4-tuple of points in convex position forms at least one obtuse angle or four right angles; and each 4-tuple of points not in convex position forms at least two obtuse angles. Thus, the total number of obtuse angles in S is at least (cr(S)−2(n 2)/4)·1+((n 4)−cr(S))·2 n−3 , where we divide by n−3 because each obtuse angle is counted n−3 times. Simplifying gives the claimed bound.  References [1] B.M. Ábrego, M. Cetina, S. Fernández-Merchant, J. Leaños, G. Salazar, 3-symmetric and 3decomposable geometric drawings of Kn , Discrete Applied Mathematics 158 (2010), 12401258. [2] B.M. Ábrego, M. Cetina, S. Fernández-Merchant, J. Leaños, G. Salazar, On (≤k) -edges, crossings, and halving lines of geometric drawings of Kn , Discrete and Computational Geometry 48 (2012), 192215. [3] J.H. Conway, H.T. Croft, P. Erd®s, M.J.T. Guy, On the distribution of values of angles determined by coplanar points, Journal of the London Mathematical Society (2) 19 (1979), 137143. [4] P. Erd®s, Z. Füredi, The greatest angle among n points in the d -dimensional Euclidean space, Annals of Discrete Mathematics 17 (1983), 275283. [5] B. Grünbaum, G.C. Shephard, Rotation and winding numbers for planar polygons and curves, Transactions of the American Mathematical Society 322 (1990), 169187. [6] R. Guy. Unsolved problems in number theory , Third Edition, Springer, New York, 2004. 90