On Triple Intersections of Three Families of Unit Circles

详细信息    查看全文

• 作者：Orit E. Raz ; Micha Sharir ; József Solymosi
• 关键词：Combinatorial geometry ; Incidences ; Unit circles
• 刊名：Discrete and Computational Geometry
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：54
• 期：4
• 页码：930-953
• 全文大小：716 KB
• 参考文献：1.Cox, D.A., Little, J., O’Shea, D.: Using Algebraic Geometry, 2nd edn. Springer, Heidelberg (2005)MATH
  2.Elekes, G.: Sums versus products in number theory, algebra and Erd?s geometry—a survey. In: Paul Erd?s and His Mathematics II, vol. 11, pp. 241-90. Bolyai Mathematical Society Studies, Budapest (2002)
  3.Elekes, G., Rónyai, L.: A combinatorial problem on polynomials and rational functions. J. Comb. Theory, Ser. A 89, 1-0 (2000)MATH CrossRef
  4.Elekes, G., Simonovits, M., Szabó, E.: A combinatorial distinction between unit circles and straight lines: how many coincidences can they have? Comb. Probab. Comput. 18, 691-05 (2009)MATH CrossRef
  5.Elekes, G., Szabó, E.: How to find groups? (And how to use them in Erd?s geometry?). Combinatorica 32, 537-71 (2012)MATH MathSciNet CrossRef
  6.Milnor, J.: On the Betti numbers of real varieties. Proc. Am. Math. Soc. 15(2), 275-80 (1964)MATH MathSciNet CrossRef
  7.Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley-Interscience, New York (1995)MATH CrossRef
  8.Pach, J., Sharir, M.: On the number of incidences between points and curves. Comb. Probab. Comput. 7, 121-27 (1998)MATH MathSciNet CrossRef
  9.Raz, O.E., Sharir, M.: Unit-area triangles: theme and variations. In: Proceedings of the 31st Annual Symposium on Computational Geometry, pp. 569-83 (2015). http://?arxiv.?org/?abs/-501.-0379
  10.Raz, O.E., Sharir, M., Solymosi, J.: Polynomials vanishing on grids: the Elekes–Rónyai problem revisited. Am. J. Math. (2015). http://?arxiv.?org/?abs/-401.-419
  11.Raz, O.E., Sharir, M., de Zeeuw, F.: Polynomials vanishing on Cartesian products: the Elekes–Szabó Theorem revisited. In: Proceedings of the 31st Annual Symposium on Computational Geometry, pp. 522-36 (2015). http://?arxiv.?org/?abs/-504.-5012
  12.Schwartz, J.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701-17 (1980)MATH CrossRef
  13.Sharir, M., Sheffer, A., Solymosi, J.: Distinct distances on two lines. J. Comb. Theory, Ser. A 20, 1732-736 (2013)MathSciNet CrossRef
  14.Sharir, M., Solymosi, J.: Distinct distances from three points. http://?arxiv.?org/?abs/-308.-814
  15.Székely, L.: Crossing numbers and hard Erd?s problems in discrete geometry. Comb. Probab. Comput. 6, 353-58 (1997)MATH CrossRef
  16.Thom, R.: Sur l’homologie des variétés algebriques réelles. In: Cairns, S.S. (ed.) Differential and Combinatorial Topology, pp. 255-65. Princeton University Press, Princeton (1965)
  17.Zippel, R.: An explicit separation of relativised random polynomial time and relativised deterministic polynomial time. Inf. Process. Lett. 33(4), 207-12 (1989)MATH MathSciNet CrossRef
  
• 作者单位：Orit E. Raz (1)
  Micha Sharir (1)
  József Solymosi (2)
  
  1. School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel
  2. Department of Mathematics, University of British Columbia, Vancouver, BC, V6T 1Z4, Canada
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer New York
• ISSN：1432-0444

文摘

Let \(p_1,p_2,p_3\) be three distinct points in the plane, and, for \(i=1,2,3\), let \(\mathcal {C}_i\) be a family of n unit circles that pass through \(p_i\). We address a conjecture made by Székely, and show that the number of points incident to a circle of each family is \(O(n^{11/6})\), improving an earlier bound for this problem due to Elekes et al. (Comb Probab Comput 18:691-05, 2009). The problem is a special instance of a more general problem studied by Elekes and Szabó (Combinatorica 32:537-71, 2012) [and by Elekes and Rónyai (J Comb Theory Ser A 89:1-0, 2000)]. Keywords Combinatorial geometry Incidences Unit circles