Hostname: page-component-7b7567c8c-mnklg Total loading time: 0 Render date: 2026-11-12T14:59:59.941Z Has data issue: false hasContentIssue false
  • English
  • Français

On a Question of Bourgain about Geometric Incidences

Published online by Cambridge University Press:  01 July 2008

JÓZSEF SOLYMOSI and
CSABA D. TÓTH
JÓZSEF SOLYMOSI
Affiliation:
Department of Mathematics, University of British Columbia, 1984 Mathematics Road, Vancouver, BC, CanadaV6T 1Z2 (e-mail: solymosi@math.ubc.ca)
CSABA D. TÓTH
Affiliation:
Department of Mathematics, University of Calgary, 2500 University Drive NW, Calgary, AB, CanadaT2N 1N4 (e-mail: cdtoth@ucalgary.ca)
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.

Given a set of s points and a set of n2 lines in three-dimensional Euclidean space such that each line is incident to n points but no n lines are coplanar, we show that s = Ω(n11/4). This is the first non-trivial answer to a question recently posed by Jean Bourgain.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 4 , July 2008, pp. 619 - 625
Copyright
Copyright © Cambridge University Press 2008

References

[1]Agarwal, P. K. and Aronov, B. (1992) Counting facets and incidences. Discrete Comput. Geom. 7 359–369.CrossRefGoogle Scholar
[2]Agarwal, P., Nevo, E., Pach, J., Pinchasi, R., Sharir, M. and Smorodinsky, S. (2004) Lenses in arrangements of pseudocircles and their applications. J. Assoc. Comput. Mach. 51 139–186.CrossRefGoogle Scholar
[3]Bennett, J., Carbery, A. and Tao, T. (2006) On the multilinear restriction and Kakeya conjectures. Acta Mathematica 196 261–302.CrossRefGoogle Scholar
[4]Bourgain, J. (1999) On the dimension of Kayela sets and related maximal inequalities. Geom. Funct. Anal. 9 256–282.CrossRefGoogle Scholar
[5]Bourgain, J., Katz, N. and Tao, T. (2004) A sum-product estimate in finite fields, and applications. Geom. Funct. Anal. 14 27–57.CrossRefGoogle Scholar
[6]Braß, P. and Knauer, C. (2003) On counting point–hyperplane incidences. Comput. Geom. Theory Appl. 25 13–20.CrossRefGoogle Scholar
[7]Chazelle, B. (2005) Cuttings. In Handbook of Data Structures and Applications, CRC Press, Boca Raton, FL, pp. 1–25.Google Scholar
[8]Chazelle, B. and Friedman, J. (1990) A deterministic view of random sampling and its use in geometry. Combinatorica 10 229–249.CrossRefGoogle Scholar
[9]Clarkson, K. L. and Shor, P. W. (1989) Applications of random sampling in computational geometry II. Discrete Comput. Geom. 4 387–421.CrossRefGoogle Scholar
[10]Croot, E. and Lev, V. F. (2004) Problems presented at the Workshop on Recent Trends in Additive Combinatorics, American Institute of Mathematics, Palo Alto, CA.Google Scholar
[11]Edelsbrunner, H., Guibas, L. J. and Sharir, M. (1990) The complexity of many cells in arrangements of planes and related problems. Discrete Comput. Geom. 5 197–216.CrossRefGoogle Scholar
[12]Edelsbrunner, H. and Haussler, D. (1986) The complexity of cells in three-dimensional arrangements. Discrete Math. 60 139–146.CrossRefGoogle Scholar
[13]Elekes, G. and Tóth, C. D. (2005) Incidences of not-too-degenerate hyperplanes. In Proc. 21st ACM Sympos. Comput. Geom., ACM Press, pp. 16–21.Google Scholar
[14]Feldman, S. and Sharir, M. (2005) An improved bound for joints in arrangements of lines in space. Discrete Comput. Geom. 33 307–320.CrossRefGoogle Scholar
[15]Hilbert, D. (1952) Geometry and the Imagination, Chelsea Publishing Company, New York.Google Scholar
[16]KővariT., T. T., T.Sós, V. and Turán,, P. (1954) On a problem of K. Zarankiewicz. Colloquium Math. 3 50–57.CrossRefGoogle Scholar
[17]Matoušek, J. (2002) Lectures on Discrete Geometry, Springer.CrossRefGoogle Scholar
[18]Pach, J. and Sharir, M. (1998) On the number of incidences between points and curves. Combin. Probab. Comput. 7 121–127.CrossRefGoogle Scholar
[19]Pach, J. and Sharir, M. (2004) Geometric incidences. In Towards a Theory of Geometric Graphs, Vol. 342 of Contemporary Mathematics, AMS, pp. 185–223.CrossRefGoogle Scholar
[20]Sharir, M. (1994) On joints in arrangements of lines in space and related problems. J. Combin. Theory Ser. A 67 89–99.CrossRefGoogle Scholar
[21]Sharir, M. and Welzl, E. (2004) Point–line incidences in space. Combin. Probab. Comput. 13 203–220.CrossRefGoogle Scholar
[22]Solymosi, J. and Tóth, C. D. (2006) Distinct distances in homogeneous sets in Euclidean space. Discrete Comput. Geom. 35 537–549.CrossRefGoogle Scholar
[23]Solymosi, J. and Vu, V. H. (2004) Distinct distances in high dimensional homogeneous sets. In Towards a Theory of Geometric Graphs, Vol. 342 of Contemporary Mathematics, AMS, pp. 259–263.CrossRefGoogle Scholar
[24]Székely, L. A. (1997) Crossing numbers and hard Erdős problems in discrete geometry. Combin. Probab. Comput. 6 353–358.CrossRefGoogle Scholar
[25]Szemerédi, E. and Trotter, W. T. Jr (1983) Extremal problems in discrete geometry. Combinatorica 3 381–392.CrossRefGoogle Scholar
[26]Wolff, T. H. (1999) Recent work connected with the Kakeya problem. In Prospects in Mathematics: Invited Talks on the Occasion of the 250th Anniversary of Princeton University (Rossi, H., ed.), AMS, pp. 129–162.Google Scholar
[27]Wolff, T. H. (2003) Lectures in Harmonic Analysis (Łaba, I. and Shubin, C., eds), Vol. 29 of University Lecture Series, AMS.CrossRefGoogle Scholar