×

zbMATH — the first resource for mathematics

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.
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)
PDF BibTeX XML Cite
Full Text: DOI
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
[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)
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.