Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The Number of Unit-Area Triangles in the Plane: Theme and Variation

  • Original Paper
  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

We show that the number of unit-area triangles determined by a set S of n points in the plane is O(n20/9), improving the earlier bound O(n9/4) of Apfelbaum and Sharir [2]. We also 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 Ω(n2), for any triple of lines (it is always O(n2) in this case).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. Apfelbaum: Geometric Incidences and Repeated Configurations, Ph.D. Dissertation, School of Computer Science, Tel Aviv University, 2013.

    Google Scholar 

  2. R. Apfelbaum and M. Sharir: An improved bound on the number of unit-area triangles, Discrete Comput. Geom. 44 (2010), 753–761.

    Article  MathSciNet  MATH  Google Scholar 

  3. A. Dumitrescu, M. Sharir and Cs. D. Tóth: Extremal problems on triangle areas in two and three dimensions, J. Combinat. Theory, Ser. A 116 (2009), 1177–1198.

    Article  MathSciNet  MATH  Google Scholar 

  4. G. Elekes and L. Rónyai: A combinatorial problem on polynomials and rational functions, J. Combinat. Theory Ser. A 89 (2000), 1–20.

    Article  MathSciNet  MATH  Google Scholar 

  5. G. Elekes and E. Szabó: How to find groups? (And how to use them in Erdős geometry?), Combinatorica 32 (2012), 537–571.

    Article  MathSciNet  MATH  Google Scholar 

  6. P. Erdős and G. Purdy: Some extremal problems in geometry, J. Combinat. Theory 10 (1971), 246–252.

    Article  MathSciNet  MATH  Google Scholar 

  7. P. Erdős and G. Purdy: Extremal problems in combinatorial geometry, in: Handbook of Combinatorics (R. Graham, M. Grötschel and L. Lovász, editors), Vol. 1, 809–874, Elsevier, Amsterdam, 1995.

    Google Scholar 

  8. J. Pach and M. Sharir: Repeated angles in the plane and related problems, J. Combinat. Theory Ser. A 59 (1992), 12–22.

    Article  MathSciNet  MATH  Google Scholar 

  9. O. E. Raz and M. Sharir: The number of unit-area triangles in the plane: Theme and variations, Proc. 31st Annu. Sympos. Comput. Geom., 2015, 569–583. Also in arXiv:1501.00379.

    Google Scholar 

  10. O. E. Raz, M. Sharir and I. Shkredov: On the number of unit-area triangles spanned by convex grids in the plane, in arXiv:1504.06989.

  11. O. E. Raz, M. Sharir and J. Solymosi: Polynomials vanishing on grids: The Elekes-Rónyai problem revisited, Amer. J. Math. 138 (2016), 1029–1065. Also in Proc. 30th Annu. Sympos. Comput. Geom., 2014, 251-260.

    Article  MathSciNet  MATH  Google Scholar 

  12. O. E. Raz, M. Sharir and F. de Zeeuw: Polynomials vanishing on Cartesian products: The Elekes-Szabó Theorem revisited, Duke Math. J., to appear. Also in arXiv:1504.05012.

  13. J. Solymosi and T. Tao: An incidence theorem in higher dimensions, Discrete Comput. Geom. 48 (2012), 255–280.

    Article  MathSciNet  MATH  Google Scholar 

  14. J. Solymosi and F. de Zeeuw: Incidence bounds for complex algebraic curves on Cartesian products, arXiv:1502.05304v2.

  15. E. Szemerédi and W. T. Trotter: Extremal problems in discrete geometry, Combinatorica 3 (1983), 381–392.

    Article  MathSciNet  MATH  Google Scholar 

  16. J. Zahl: A Szemerédi-Trotter type theorem in R4, Discrete. Comput. Geom. 54 (2015), 513–572.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science, Tel Aviv University, Tel Aviv, 69978, Israel

    Orit E. Raz & Micha Sharir

Authors
  1. Orit E. Raz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Micha Sharir
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Orit E. Raz.

Additional information

Work on this paper by Orit E. Raz and Micha Sharir was supported by Grant 892/13 from the Israel Science Foundation and by the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11). Work by Orit E. Raz was also supported by a Shulamit Aloni Fellowship from the Israeli Ministry of Science. Work by Micha Sharir was also supported by Grant 2012/229 from the U.S.-Israel Binational Science Foundation and by the Hermann Minkowski-MINERVA Center for Geometry at Tel Aviv University. Part of this research was performed while the authors were visiting the Institute for Pure and Applied Mathematics (IPAM), which is supported by the National Science Foundation. A preliminary version of this paper has appeared in Proc. 31st Annu. Sympos. Comput. Geom., 2015.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Raz, O.E., Sharir, M. The Number of Unit-Area Triangles in the Plane: Theme and Variation. Combinatorica 37, 1221–1240 (2017). https://doi.org/10.1007/s00493-016-3440-8

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00493-016-3440-8

Mathematics Subject Classification (2000)

Search

Navigation