Abstract
We prove that the number of incidences between m points and n bounded-degree curves with k degrees of freedom in ℝd is \(\left.+m+n\right),\) where the constant of proportionality depends on k, ε and d, for any ε > 0, provided that no j-dimensional surface of degree c j (k,d,ε), a constant parameter depending on k, d, j, and ε, contains more than q j input curves, and that the q j ’s satisfy certain mild conditions.
This bound generalizes a recent result of Sharir and Solomon [20] concerning point-line incidences in four dimensions (where d = 4 and k = 2), and partly generalizes a recent result of Guth [8] (as well as the earlier bound of Guth and Katz [10]) in three dimensions (Guth’s three-dimensional bound has a better dependency on q). It also improves a recent d-dimensional general incidence bound by Fox, Pach, Sheffer, Suk, and Zahl [7], in the special case of incidences with algebraic curves. Our results are also related to recent works by Dvir and Gopi [4] and by Hablicsek and Scherr [11] concerning rich lines in high-dimensional spaces.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aronov, B., Koltun, V., Sharir, M.: Incidences between points and circles in three and higher dimensions. Discrete Comput. Geom. 33, 185–206 (2005)
Basu, S., Sombra, M.: Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions. arXiv:1406.2144
Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., Welzl, E.: Combinatorial complexity bounds for arrangements of curves and spheres. Discrete Comput. Geom. 5, 99–160 (1990)
Dvir, Z., Gopi, S.: On the number of rich lines in truly high dimensional sets. In: Proc. 31st Annu. Sympos. Comput. Geom. (2015, to appear)
Elekes, G., Kaplan, H., Sharir, M.: On lines, joints, and incidences in three dimensions. J. Combinat. Theory, Ser. A 118, 962–977 (2011); Also in arXiv:0905.1583
Erdős, P.: On sets of distances of n points. Amer. Math. Monthly 53, 248–250 (1946)
Fox, J., Pach, J., Sheffer, A., Suk, A., Zahl, J.: A semi-algebraic version of Zarankiewicz’s problem. arXiv:1407.5705
Guth, L.: Distinct distance estimates and low-degree polynomial partitioning. Discrete Comput. Geom. 53, 428–444 (2015); Also in arXiv:1404.2321
Guth, L., Katz, N.H.: Algebraic methods in discrete analogs of the Kakeya problem. Advances Math. 225, 2828–2839 (2010); Also in arXiv:0812.1043
Guth, L., Katz, N.H.: On the Erdős distinct distances problem in the plane. Annals Math. 181, 155–190 (2015); Also in arXiv:1011.4105
Hablicsek, M., Scherr, Z.: On the number of rich lines in high dimensional real vector spaces. arXiv:1412.7025
Harris, J.: Algebraic Geometry: A First Course, vol. 133. Springer, New York (1992)
Kaplan, H., Matoušek, J., Safernová, Z., Sharir, M.: Unit distances in three dimensions. Combinat. Probab. Comput. 21, 597–610 (2012); Also in arXiv:1107.1077
Kaplan, H., Matoušek, J., Sharir, M.: Simple proofs of classical theorems in discrete geometry via the Guth–Katz polynomial partitioning technique. Discrete Comput. Geom. 48, 499–517 (2012); Also in arXiv:1102.5391
Matoušek, J.: Lectures on Discrete Geometry. Springer, Heidelberg (2002)
Nilov, F., Skopenkov, M.: A surface containing a line and a circle through each point is a quadric. arXiv:1110:2338
Pach, J., Sharir, M.: On the number of incidences between points and curves. Combinat. Probab. Comput. 7, 121–127 (1998)
Pach, J., Sharir, M.: Geometric incidences. In: Pach, J. (ed.) Towards a Theory of Geometric Graphs. Contemporary Mathematics, vol. 342, pp. 185–223. Amer. Math. Soc., Providence (2004)
Sharir, M., Sheffer, A., Zahl, J.: Improved bounds for incidences between points and circles. Combinat. Probab. Comput. 24, 490–520 (2015); Also in Proc. 29th ACM Symp. on Computational Geometry, 97–106, arXiv:1208.0053 (2013)
Sharir, M., Solomon, N.: Incidences between points and lines in four dimensions. In: Proc. 30th ACM Sympos. on Computational Geometry, pp. 189–197 (2014)
Sharir, M., Solomon, N.: Incidences between points and lines in four dimensions. J. AMS, arXiv:1411.0777 (submitted)
Sharir, M., Solomon, N.: Incidences between points and lines in three dimensions. In: Proc. 31st ACM Sympos. on Computational Geometry (2015, to appear); Also Discrete Comput. Geom. arXiv:1501.02544 (submitted)
Sharir, M., Solomon, N.: Incidences between points and lines on a two-dimensional variety in three dimensions. Combinatorica, arXiv:1501.01670 (submitted)
Solymosi, J., Tao, T.: An incidence theorem in higher dimensions. Discrete Comput. Geom. 48, 255–280 (2012)
Spencer, J., Szemerédi, E., Trotter, W.T.: Unit distances in the Euclidean plane. In: Bollobás, B. (ed.) Graph Theory and Combinatorics, pp. 293–303. Academic Press, New York (1984)
Székely, L.: Crossing numbers and hard Erdős problems in discrete geometry. Combinat. Probab. Comput. 6, 353–358 (1997)
Szemerédi, E., Trotter, W.T.: Extremal problems in discrete geometry. Combinatorica 3, 381–392 (1983)
Tao, T.: From rotating needles to stability of waves: Emerging connections between combinatorics, analysis, and PDE. Notices AMS 48(3), 294–303 (2001)
Zahl, J.: An improved bound on the number of point-surface incidences in three dimensions. Contrib. Discrete Math. 8(1) (2013); Also in arXiv:1104.4987
Zahl, J.: A Szemerédi-Trotter type theorem in ℝ4, arXiv:1203.4600
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sharir, M., Sheffer, A., Solomon, N. (2015). Incidences with Curves in ℝd . In: Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015. Lecture Notes in Computer Science(), vol 9294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48350-3_81
Download citation
DOI: https://doi.org/10.1007/978-3-662-48350-3_81
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48349-7
Online ISBN: 978-3-662-48350-3
eBook Packages: Computer ScienceComputer Science (R0)