On rich points and incidences with restricted sets of lines in 3-space

DOI10.20382/JOCG.V13I2A4MaRDI QIDQ5044451zbMATH OpenFDO

Authors Noam Solomon, Micha Sharir

Publication date 31 October 2022

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

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Erd?s problems and related topics of discrete geometry (52C10) Algebraic functions and function fields in algebraic geometry (14H05) Combinatorial complexity of geometric structures (52C45)

Abstract: Let $L$ be a set of $n$ lines in $R^3$ that is contained, when represented as points in the four-dimensional Pl"ucker space of lines in $R^3$, in an irreducible variety $T$ of constant degree which is emph{non-degenerate} with respect to $L$ (see below). We show: medskip

oindent{�f (1)} If $T$ is two-dimensional, the number of $r$-rich points (points incident to at least $r$ lines of $L$) is $O(n^{4/3+epsilon}/r^2)$, for $rge3$ and for any $epsilon>0$, and, if at most $n^{1/3}$ lines of $L$ lie on any common regulus, there are at most $O(n^{4/3+epsilon})$ $2$-rich points. For $r$ larger than some sufficiently large constant, the number of $r$-rich points is also $O(n/r)$. As an application, we deduce (with an $epsilon$-loss in the exponent) the bound obtained by Pach and de Zeeuw (2107) on the number of distinct distances determined by $n$ points on an irreducible algebraic curve of constant degree in the plane that is not a line nor a circle. medskip oindent{�f (2)} If $T$ is two-dimensional, the number of incidences between $L$ and a set of $m$ points in $R^3$ is $O(m+n)$. medskip

oindent{�f (3)} If $T$ is three-dimensional and nonlinear, the number of incidences between $L$ and a set of $m$ points in $R^3$ is $Oleft(m^{3/5}{n}^{3/5}+(m^{11/15}{n}^{2/5}+m^{1/3}{n}^{2/3})s^{1/3}+m+night)$, provided that no plane contains more than $s$ of the points. When $s=O(min{n}^{3/5}/m^{2/5},m^{1/2})$, the bound becomes $O(m^{3/5}{n}^{3/5}+m+n)$. As an application, we prove that the number of incidences between $m$ points and $n$ lines in $R^4$ contained in a quadratic hypersurface (which does not contain a hyperplane) is $O(m^{3/5}{n}^{3/5}+m+n)$. The proofs use, in addition to various tools from algebraic geometry, recent bounds on the number of incidences between points and algebraic curves in the plane.

Recommendations

• Incidences between points and lines on two- and three-dimensional varieties
• Incidences between points and lines in R4
• Incidences between points and lines in \({\mathbb {R}}^4\)
• Incidences between points and lines in three dimensions
• Algebraic curves, rich points, and doubly-ruled surfaces

Cited in

(12)

• Incidences between points and lines on two- and three-dimensional varieties
• Point-curve incidences in the complex plane
• On the number of rich lines in high dimensional real vector spaces
• On the number of rich lines in truly high dimensional sets
• On the use of the Klein quadric for geometric incidence problems in two dimensions
• Curves in \(\mathbb {R}^4\) and two-rich points
• A note on rich lines in truly high dimensional sets
• Distinct distance estimates and low degree polynomial partitioning
• Highly incidental patterns on a quadratic hypersurface in \(\mathbb{R}^4\)
• On incidences of lines in regular complexes
• Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances
• Improved bounds for pencils of lines

This page was built for publication: On rich points and incidences with restricted sets of lines in 3-space

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