The number of unit-area triangles in the plane: Theme and variations

2015/01/02 by Orit E. Raz, Micha Sharir, Raz, Orit E. +1 · 1 citation
Computer Science · Mathematics · #52C10 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #cs.CG #cs.DM #math.CO #math.MG #msc:52C10

paper · pdf · doi:10.48550/arxiv.1501.00379

arxiv created 2015/04/11 · arxiv updated 2015/04/14

Abstract

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 [Discrete Comput. Geom., 2010]. 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 Ω(n²), for any triple of lines (it is always O(n²) in this case). (ii) We show that if S is a \em convex grid of the form A× B, where A, B are \em 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.

Cited by

• On the number of unit-area triangles spanned by convex grids in the plane

Related

• Improved estimates on the number of unit perimeter triangles
• On the number of unit-area triangles spanned by convex grids in the plane
• Triangle areas in line arrangements
• On the number of classes of triangles determined by N points in \R²
• Plane point sets with many squares or isosceles right triangles