Triangle areas in line arrangements. (English) Zbl 1448.52019
Summary: A widely investigated subject in combinatorial geometry, originated from Erdős, is the following. Given a point set \(P\) of cardinality \(n\) in the plane, how can we describe the distribution of the determined distances? This has been generalized in many directions.
In this paper we propose the following variants. What is the maximum number of triangles of unit area, maximum area or minimum area, that can be determined by an arrangement of \(n\) lines in the plane?
We prove that the order of magnitude for the maximum occurrence of unit areas lies between \(\varOmega (n^2)\) and \(O(n^{9/ 4+\varepsilon})\), for every \(\varepsilon > 0\). This result is strongly connected to additive combinatorial results and Szemerédi-Trotter type incidence theorems. Next we show an almost tight bound for the maximum number of minimum area triangles. Finally, we present lower and upper bounds for the maximum area and distinct area problems by combining algebraic, geometric and combinatorial techniques.
In this paper we propose the following variants. What is the maximum number of triangles of unit area, maximum area or minimum area, that can be determined by an arrangement of \(n\) lines in the plane?
We prove that the order of magnitude for the maximum occurrence of unit areas lies between \(\varOmega (n^2)\) and \(O(n^{9/ 4+\varepsilon})\), for every \(\varepsilon > 0\). This result is strongly connected to additive combinatorial results and Szemerédi-Trotter type incidence theorems. Next we show an almost tight bound for the maximum number of minimum area triangles. Finally, we present lower and upper bounds for the maximum area and distinct area problems by combining algebraic, geometric and combinatorial techniques.
MSC:
| 52C30 | Planar arrangements of lines and pseudolines (aspects of discrete geometry) |
| 52C10 | Erdős problems and related topics of discrete geometry |
| 52A38 | Length, area, volume and convex sets (aspects of convex geometry) |
References:
| [1] | Akopyan, A. V.; Zaslavsky, A. A., Geometry of conics, Amer. Math. Soc. (2007) · Zbl 1131.51008 |
| [2] | Apfelbaum, R.; Sharir, M., An improved bound on the number of unit area triangles, Discrete Comput. Geom., 44, 4, 753-761 (2010) · Zbl 1202.52017 |
| [3] | Bader, J.; Clement, G., Tighter upper bound for the number of Kobon triangles, (Knowles, J.; Corne, D.; Deb, K., Multiobjective Problem Solving from Nature: From Concepts to Applications (2007), Springer), 177-200 |
| [4] | Brass, P.; Moser, W. O.J.; Pach, J., Research Problems in Discrete Geometry (2005), Springer · Zbl 1086.52001 |
| [5] | Brass, P.; Rote, G.; Swanepoel, K. J., Triangles of extremal area or perimeter in a finite planar point set, Discrete Comput. Geom., 26, 1, 51-58 (2001) · Zbl 0982.52014 |
| [6] | Conlon, D.; Fox, J.; Gasarch, W.; Harris, D. G.; Ulrich, D.; Zbarsky, S., Distinct volume subsets, SIAM J. Discrete Math., 29, 1, 472-480 (2015) · Zbl 1455.52015 |
| [7] | Dumitrescu, A.; Sharir, M.; Tóth, C. D., Extremal problems on triangle areas in two and three dimensions, J. Combin. Theory Ser. A, 116, 7, 1177-1198 (2009) · Zbl 1179.52026 |
| [8] | Erdős, P., On sets of distances of \(n\) points, Amer. Math. Monthly, 53, 5, 248-250 (1946) · Zbl 0060.34805 |
| [9] | Erdős, P., Néhány geometriai problémáról, Math. Lapok, 8, 86-92 (1957), (On some geometrical problems, in Hungarian) · Zbl 0102.37004 |
| [10] | Erdős, P.; Lovász, L.; Vesztergombi, K., On the graph of large distances, Discrete Comput. Geom., 4, 6, 541-549 (1989) · Zbl 0694.05031 |
| [11] | Erdős, P.; Purdy, G., Some extremal problems in geometry, J. Combin. Theory Ser. A, 10, 246-252 (1971) · Zbl 0219.05006 |
| [12] | Erdös, P.; Purdy, G.; Straus, E. G., On a problem in combinatorial geometry, Discrete Math., 40, 1, 45-52 (1982) · Zbl 0501.52009 |
| [13] | Forge, D.; Alfonsin, J. R., Straight line arrangements in the real projective plane, Discrete Comput. Geom., 20, 2, 155-161 (1998) · Zbl 0921.52004 |
| [14] | Füredi, Z.; Palásti, I., Arrangements of lines with a large number of triangles, Proc. Amer. Math. Soc., 92, 561-566 (1984) · Zbl 0521.51003 |
| [15] | Iosevich, A.; Rudnev, M.; Zhai, Y., Areas of triangles and Beck’s theorem in planes over finite fields, Combinatorica, 35, 3, 295-308 (2015) · Zbl 1363.52015 |
| [16] | Martínez-Sandoval, L.; E., Roldán-Pensado, Points defining triangles with distinct circumradii, Acta Math. Hungar., 145, 1, 136-141 (2015) · Zbl 1340.52025 |
| [17] | Martínez-Sandoval, L.; Raggi, M.; Roldán-Pensado, E., A sunflower anti-Ramsey theorem and its applications (2015), ArXiv e-prints ArXiv:1505.05170 |
| [18] | Pach, J.; Sharir, M., Repeated angles in the plane and related problems, J. Combin. Theory Ser. A, 59, 12-22 (1992) · Zbl 0749.52014 |
| [19] | Pach, J.; Sharir, M., On the number of incidences between points and curves, Combin. Probab. Comput., 7, 121-127 (1998) · Zbl 0901.52016 |
| [20] | Pick, G., Geometrisches zur Zahlenlehre, Sitzungsberichte des deutschen naturwissenschaftlich-medicinischen Vereines für Böhmen Lotos in Prag. (Neue Folge), 19, 311-319 (1899) · JFM 33.0216.01 |
| [21] | Raz, O. E.; Sharir, M., The number of unit-area triangles in the plane: Theme and variation, Combinatorica, 37, 6, 1221-1240 (2017) · Zbl 1399.52032 |
| [22] | Sharir, M.; Zahl, J., Cutting algebraic curves into pseudo-segments and applications, J. Combin. Theory Ser. A, 150, 1-35 (2017) · Zbl 1362.05037 |
| [23] | Zamfirescu, C. T., Congruent triangles in arrangements of lines, Ars Math. Contemp., 14, 2, 359-373 (2017) · Zbl 1396.52022 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
