2026-07-29T13:01:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5112 2024-03-06T10:35:55Z ddc:004 open_access

The Number of Unit-Area Triangles in the Plane: Theme and Variations Raz, Orit E. Sharir, Micha Combinatorial geometry incidences repeated configurations We show that the number of unit-area triangles determined by a set S of n points in the plane is O(n^{20/9}), improving the earlier bound O(n^{9/4}) of Apfelbaum and Sharir. We also consider two special cases of this problem: (i) We show, using a somewhat subtle construction, that if S consists of points on three lines, the number of unit-area triangles that S spans can be Omega(n^2), for any triple of lines (it is always O(n^2) in this case). (ii) We show that if S is a convex grid of the form A x B, where A, B are convex sets of n^{1/2} real numbers each (i.e., the sequences of differences of consecutive elements of A and of B are both strictly increasing), then S determines O(n^{31/14}) unit-area triangles. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Orit E. Raz and Micha Sharir 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.569 urn:nbn:de:0030-drops-51125 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.569 eng https://creativecommons.org/licenses/by/3.0/legalcode