An improved bound on the number of unit area triangles

ABSTRACT

We show that the number of unit-area triangles determined by a set of n points in the plane is O(n^9/4+ε), for any ε>0, improving the recent bound O(n^44/19) of Dumitrescu et al.

REFERENCES

• 1: B. Chazelle, Cuttings, In "Handbook of Data Structures and Applications" (D. Mehta and S. Sahni, editors), chap. 25, Chapman and Hall/CRC Press, 2005.
• 2: Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
• 3: Adrian Dumitrescu , Micha Sharir , Csaba D. Tóth, Extremal problems on triangle areas in two and three dimensions, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA [doi>10.1145/1377676.1377709]
• 4: P. Erdos and G. Purdy, Some extremal problems in geometry, J. Combinat. Theory 10 (1971), 246--252.
• 5: Paul Erdős , George Purdy, Extremal problems in combinatorial geometry, Handbook of combinatorics (vol. 1), MIT Press, Cambridge, MA, 1996
• 6: T. Kovari, V. T. Sos, and P. Turan, On a problem of K. Zarankiewicz, Colloquium Math. 3 (1954), 50--57.
• 7: János Pach , Micha Sharir, Repeated angles in the plane and related problems, Journal of Combinatorial Theory Series A, v.59 n.1, p.12-22, Jan. 1992 [doi>10.1016/0097-3165(92)90094-B]
• 8: I. R. Shafarevich, Basic Algebraic Geometry, Springer-Verlag, 1977.
• 9: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 10: E. Szemeredi and W. T. Trotter, Extremal problems in discrete geometry, Combinatorica 3 (1983), 381--392.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems

General Terms:
Theory

Keywords:
combinatorial geometry, geometric incidences, repeated configurations, unit-area triangles