Dumitrescu 2009 extremal problems triangle areas two three

../

theorem_1: Dumitrescu, Sharir and Tóth's theorem that n points in the plane span O(n^{2+6/19}) = O(n^{2.3158}) triangles of unit area, an upper bound for the equal-area triangle count of Problem 1086.

theorem_10: Dumitrescu, Sharir and Tóth's theorem that the triangles of maximum area spanned by a set of n points in three-space and incident to a fixed point of the set number O(n^{4/3+eps}) for any eps > 0.

theorem_11: Dumitrescu, Sharir and Tóth's bounds that n points in three-space span O(n^{7/3+eps}) triangles of maximum area for any eps > 0, and that for all n

= 3 some n points span Omega(n^{4/3}) of them.

theorem_12: Dumitrescu, Sharir and Tóth's theorem that any n points in three-space, not all on a line, determine Omega(n^{2/3}/beta(n)) triangles of distinct areas, all sharing a common side, for an extremely slowly growing beta(n).

theorem_13: Dumitrescu, Sharir and Tóth's theorem that n lines in the plane determine at most O(n^{7/3}) unit-area triangles, and that for every n >= 3 some n lines determine Omega(n^2) of them.

theorem_2: Dumitrescu, Sharir and Tóth's construction, for every n >= 3, of n points in convex position in the plane spanning Omega(n log n) triangles of unit area.

theorem_3: Dumitrescu, Sharir and Tóth's bound that n points in the plane span at most (2/3)(n^2 - n) triangles of minimum nonzero area, with the floor(sqrt n) by floor(sqrt n) integer grid spanning (6/pi^2 - o(1)) n^2 of them.

theorem_4: Dumitrescu, Sharir and Tóth's theorem that the number of acute triangles of minimum area determined by n points in the plane is O(n), and that this is asymptotically tight.

theorem_5: Dumitrescu, Sharir and Tóth's theorem that n points in strictly convex position in the plane determine O(n) triangles of minimum area, a bound attained up to a constant by the regular n-gon.

theorem_6: Dumitrescu, Sharir and Tóth's construction, for every n >= 3, of n points in the plane with no three collinear spanning Omega(n log n) triangles of minimum nonzero area.

theorem_7: Dumitrescu, Sharir and Tóth's theorem that n points in three-space span O(n^{17/7} beta(n)) = O(n^{2.4286}) triangles of unit area, with beta(n) of the form exp(alpha(n)^{O(1)}) for the inverse Ackermann function alpha.

theorem_8: Dumitrescu, Sharir and Tóth's theorem that n points in three-space span at most n^2 + O(n) triangles of minimum nonzero area, with constructions giving (2/3) n^2 - O(n).

theorem_9: Dumitrescu, Sharir and Tóth's construction, for every n, of n points in three-space spanning Omega(n^{4/3}) triangles of maximum area, all incident to a common point.

---

Dumitrescu, Adrian and Sharir, Micha and Tóth, Csaba D., Extremal problems on triangle areas in two and three dimensions. J. Combin. Theory Ser. A 116 (2009), no. 7, 1177--1198. DOI 10.1016/j.jcta.2009.03.008. The copy read for this card is the arXiv preprint arXiv:0710.4109v1 (22 October 2007). Its pages are cited by their printed numbers; an unnumbered title page precedes p. 1. The arXiv record carries no license field, so arXiv's assumed license applies (arXiv:0710.4109), every other right reserved.

The main planar result bounds the number of unit-area triangles spanned by n points by O(n^{2+6/19}) = O(n^{44/19}) = O(n^{2.3158}) (Theorem 1, p. 2), which the abstract calls the first breakthrough improving the O(n^{7/3}) bound of Pach and Sharir from 1992, obtained by counting incidences between the points and a four-parameter family of quadratic curves. In the plane the paper also shows that for all n >= 3 some n points in convex position span Omega(n log n) unit-area triangles (Theorem 2); that n points span at most (2/3)(n^2-n) triangles of minimum nonzero area, while the floor(sqrt n) by floor(sqrt n) integer grid spans (6/pi^2 - o(1))n^2 of them (Theorem 3); that n points span O(n) acute minimum-area triangles (Theorem 4), and n points in strictly convex position O(n) minimum-area triangles (Theorem 5), both asymptotically tight; and that for all n >= 3 some n points with no three collinear span Omega(n log n) minimum-area triangles (Theorem 6). In three dimensions it proves an O(n^{17/7} beta(n)) = O(n^{2.4286}) bound on unit-area triangles, with beta(n) of the form exp(alpha(n)^{O(1)}) for the inverse Ackermann function alpha, improving Erdos and Purdy's O(n^{8/3}) from 1971 through an analysis of point-cylinder incidences (Theorem 7); at most n^2 + O(n) minimum-area triangles, optimal up to a constant factor (Theorem 8); n-point sets with Omega(n^{4/3}) maximum-area triangles through a common point (Theorem 9), with an almost matching O(n^{4/3+eps}) bound, for every eps > 0, on the number through any one point (Theorem 10) and an O(n^{7/3+eps}) bound on all of them (Theorem 11); and, for n points not all on a line, Omega(n^{2/3}/beta(n)) triangles of distinct areas sharing a common side (Theorem 12). The conclusion shows that n lines in the plane determine O(n^{7/3}) unit-area triangles, and some n lines Omega(n^2) (Theorem 13). Tools include the Szemeredi-Trotter theorem, the crossing lemma, quasi-planar graphs and the partition technique of Clarkson et al.

Read status: claims checked for the results linked below, statements read clause by clause on the printed pages of arXiv v1; no proof is checked step by step.

Source: https://arxiv.org/abs/0710.4109.

Bears on.

• #1086: by the affine reduction of p. 1, Theorem 1 bounds the number of triangles of any one fixed positive area among n planar points by O(n^{44/19}), an upper bound on the problem's g(n). The grid of Theorem 3 gives (6/pi^2 - o(1))n^2 triangles of one area among at most n points, weaker than the Erdos-Purdy lower bound Omega(n^2 log log n) recalled on p. 1 and not proved here. The convex-position sets of Theorem 2 give only Omega(n log n), weaker still. Theorem 13 concerns lines and gives no bound on g(n); the remark on p. 23 says an o(n^{11/5}) bound in Theorem 13 would improve Theorem 1. The paper does not settle the order of g(n).

Results.

• Theorem 1 (p. 2): n points in the plane span O(n^{2+6/19}) = O(n^{2.3158}) unit-area triangles.
• Theorem 2 (p. 4): for all n >= 3, some n points in convex position span Omega(n log n) unit-area triangles.
• Theorem 3 (p. 5): n points in the plane span at most (2/3)(n^2-n) triangles of minimum nonzero area; the floor(sqrt n) by floor(sqrt n) integer grid spans (6/pi^2 - o(1))n^2 of them.
• Theorem 4 (p. 7): n points in the plane determine O(n) acute triangles of minimum area, asymptotically tight.
• Theorem 5 (p. 7): n points in strictly convex position determine O(n) minimum-area triangles, asymptotically tight.
• Theorem 6 (p. 8): for all n >= 3, some n points with no three collinear span Omega(n log n) triangles of minimum nonzero area.
• Theorem 7 (p. 9): n points in R^3 span O(n^{17/7} beta(n)) = O(n^{2.4286}) unit-area triangles.
• Theorem 8 (p. 15): n points in R^3 span at most n^2 + O(n) triangles of minimum nonzero area.
• Theorem 9 (p. 18): for any n, some n points in R^3 span Omega(n^{4/3}) maximum-area triangles, all incident to a common point.
• Theorem 10 (p. 18): the maximum-area triangles of n points in R^3 incident to a fixed point of the set number O(n^{4/3+eps}) for any eps > 0.
• Theorem 11 (p. 20): n points in R^3 span O(n^{7/3+eps}) maximum-area triangles for any eps > 0, and for all n >= 3 some n points span Omega(n^{4/3}).
• Theorem 12 (p. 20): n points in R^3, not all on a line, determine Omega(n^{2/3}/beta(n)) triangles of distinct areas, all sharing a common side.
• Theorem 13 (p. 22): n lines in the plane determine O(n^{7/3}) unit-area triangles, and for any n >= 3 some n lines determine Omega(n^2).

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.