Hostname: page-component-6898cfcb55-cbk24 Total loading time: 0 Render date: 2026-11-11T10:59:09.005Z Has data issue: false hasContentIssue false
  • English
  • Français

A Combinatorial Distinction Between Unit Circles and Straight Lines: How Many Coincidences Can they Have?

Published online by Cambridge University Press:  01 September 2009

GYÖRGY ELEKES,
MIKLÓS SIMONOVITS and
ENDRE SZABÓ
GYÖRGY ELEKES
Affiliation:
Mathematical Institute of Eötvös University, Hungary and Alfréd Rényi Mathematical Institute, Hungary (e-mail: elekes@cs.elte.hu, miki@renyi.hu and endre@renyi.hu)
MIKLÓS SIMONOVITS
Affiliation:
Mathematical Institute of Eötvös University, Hungary and Alfréd Rényi Mathematical Institute, Hungary (e-mail: elekes@cs.elte.hu, miki@renyi.hu and endre@renyi.hu)
ENDRE SZABÓ
Affiliation:
Mathematical Institute of Eötvös University, Hungary and Alfréd Rényi Mathematical Institute, Hungary (e-mail: elekes@cs.elte.hu, miki@renyi.hu and endre@renyi.hu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We give a very general sufficient condition for a one-parameter family of curves not to have n members with ‘too many’ (i.e., a near-quadratic number of) triple points of intersections. As a special case, a combinatorial distinction between straight lines and unit circles will be shown. (Actually, this is more than just a simple application; originally this motivated our results.)

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 5: New Directions in Algorithms, Combinatorics and Optimization , September 2009, pp. 691 - 705
Copyright
Copyright © Cambridge University Press 2009

References

[1]Brass, P., Moser, W. and Pach, J. (2005) Research Problems in Discrete Geometry, Springer, New York.Google Scholar
[2]Elekes, G. (1984) n points in the plane can determine n 3/2 unit circles. Combinatorica 4 131.CrossRefGoogle Scholar
[3]Elekes, G. (1995) Circle grids and bipartite graphs of distances. Combinatorica 15 167–174.CrossRefGoogle Scholar
[4]Elekes, G. (2002) Sums versus products in number theory, algebra and Erdős geometry: A survey. In Paul Erdős and his Mathematics II, Vol. 11 of Bolyai Mathematical Society Studies, pp. 241–290.Google Scholar
[5]Elekes, G. and Szabó, E. How to find groups? (And how to use them in Erdős geometry?) Accepted in Combinatorica.Google Scholar
[6]Erdős, P. (1981) Some applications of graph theory and combinatorial methods to number theory and geometry. In Algebraic Methods in Graph Theory, Vol. 25 of Coll. Math. Soc. J. Bolyai, pp. 137–148.Google Scholar
[7]Füredi, Z. and Palásti, I. (1984) Arrangements of lines with a large number of triangles. Proc. Amer. Math. Soc. 92 561–566.CrossRefGoogle Scholar
[8]Matoušek, J. (2002) Lectures on Discrete Geometry, Springer.CrossRefGoogle Scholar
[9]Pach, J. and Agarwal, P. K. (1995) Combinatorial Geometry, Wiley, New York.CrossRefGoogle Scholar
[10]Pach, J. and Sharir, M. (1990) Repeated angles in the plane and related problems. J. Combin. Theory Ser. A 59 12–22.CrossRefGoogle Scholar
[11]Spencer, J., Szemerédi, E. and Trotter, W. T. Jr, (1984, 1983) Unit distances in the Euclidean plane. In Graph Theory and Combinatorics (Cambridge 1983), Academic Press, London, pp. 293–303.Google Scholar
[12]Sylvester, J. J. (1867) Problem 2473. Math. Questions from the Educational Times 8 106–107.Google Scholar
[13]Székely, L. A. (1997) Crossing numbers and hard Erdős problems in discrete geometry. Combin. Probab. Comput. 6 353–358.CrossRefGoogle Scholar
[14]Szemerédi, E. and Trotter, W. T. Jr, (1983) Extremal problems in discrete geometry. Combinatorica 3 381–392.Google Scholar