Incidences with curves in R^d

DOI10.1007/978-3-662-48350-3_81MaRDI QIDQ3452856zbMATH OpenOpenAlexFDO

Authors Adam Sheffer, Noam Solomon, Micha Sharir

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.08267

Mathematics Subject Classification ID

Other designs, configurations (05B30) Other finite incidence structures (geometric aspects) (51E30)

Abstract: We prove that the number of incidences between $m$ points and $n$ bounded-degree curves with $k$ degrees of freedom in ${mathbbR}^d$ is [ I(m,n) =Oleft(m^{frac{k}{dk-d+1}+varepsilon}n^{frac{dk-d}{dk-d+1}}+ sum_{j=2}^{d-1} m^{frac{k}{jk-j+1}+varepsilon}n^{frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}}q_j^{frac{(d-j)(k-1)}{(d-1)(jk-j+1)}}+m+n ight), ] for any $varepsilon>0$, where the constant of proportionality depends on $k,varepsilon$ and $d$, provided that no $j$-dimensional surface of degree $le{c}_j(k,d,varepsilon)$, a constant parameter depending on $k$, $d$, $j$, and $varepsilon$, 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 concerning point-line incidences in four dimensions (where $d=4$ and $k=2$), and partly generalizes a recent result of Guth (as well as the earlier bound of Guth and Katz) in three dimensions (Guth's three-dimensional bound has a better dependency on $q_2$). It also improves a recent $d$-dimensional general incidence bound by Fox, Pach, Sheffer, Suk, and Zahl, in the special case of incidences with algebraic curves. Our results are also related to recent works by Dvir and Gopi and by Hablicsek and Scherr concerning rich lines in high-dimensional spaces.

Recommendations

• Incidences with curves in \(\mathbb{R}^d\)
• On the Number of Incidences Between Points and Curves
• Incidences between points and lines in \({\mathbb {R}}^4\)
• Incidences between points and lines on two- and three-dimensional varieties
• Incidences between points and circles in three and higher dimensions

Cites work

• A semi-algebraic version of Zarankiewicz's problem
• A surface containing a line and a circle through each point is a quadric
• A Szemerédi-Trotter type theorem in R^4
• Algebraic methods in discrete analogs of the Kakeya problem
• An improved bound on the number of point-surface incidences in three dimensions
• An incidence theorem in higher dimensions
• Combinatorial complexity bounds for arrangements of curves and spheres
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Distinct distance estimates and low degree polynomial partitioning
• Extremal problems in discrete geometry
• From rotating needles to stability of waves: emerging connections between combinatorics, analysis, and PDE
• scientific article; zbMATH DE number 52497 (Why is no real title available?)
• scientific article; zbMATH DE number 2145241 (Why is no real title available?)
• scientific article; zbMATH DE number 3893918 (Why is no real title available?)
• Improved bounds for incidences between points and circles
• Incidences between points and circles in three and higher dimensions
• Incidences between points and lines in \({\mathbb {R}}^4\)
• Incidences between points and lines in R4
• On lines, joints, and incidences in three dimensions
• On Sets of Distances of n Points
• On the Erdős distinct distances problem in the plane
• On the Number of Incidences Between Points and Curves
• On the number of rich lines in high dimensional real vector spaces
• On the number of rich lines in truly high dimensional sets
• Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions

Cited in

(11)

• A general incidence bound in \(\mathbb{R}^d\)
• Incidences between points and curves with almost two degrees of freedom
• Curves in \(\mathbb {R}^4\) and two-rich points
• Incidence bounds for complex algebraic curves on Cartesian products
• Lower bounds for incidences with hypersurfaces
• Geometric incidence theorems via Fourier analysis
• On the Number of Incidences Between Points and Curves
• An incidence theorem in higher dimensions
• Ruled surface theory and incidence geometry
• On rich points and incidences with restricted sets of lines in 3-space
• Incidences with curves in \(\mathbb{R}^d\)

This page was built for publication: Incidences with curves in \(\mathbb{R}^{d}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452856)