Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn rich points and incidences with restricted sets of lines in 3-space
140
0
0.0
(
0
)
Added by
Micha Sharir
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Let $L$ be a set of $n$ lines in $R^3$ that is contained, when represented as points in the four-dimensional Plucker 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{bf (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 $r ge 3$ 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{bf (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{bf (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 + n right)$, 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.
rate research
Read More
We prove a new upper bound on the number of $r$-rich lines (lines with at least $r$ points) in a `truly $d$-dimensional configuration of points $v_1,ldots,v_n in mathbb{C}^d$. More formally, we show that, if the number of $r$-rich lines is significantly larger than $n^2/r^d$ then there must exist a large subset of the points contained in a hyperplane. We conjecture that the factor $r^d$ can be replaced with a tight $r^{d+1}$. If true, this would generalize the classic Szemeredi-Trotter theorem which gives a bound of $n^2/r^3$ on the number of $r$-rich lines in a planar configuration. This conjecture was shown to hold in $mathbb{R}^3$ in the seminal work of Guth and Katz cite{GK10} and was also recently proved over $mathbb{R}^4$ (under some additional restrictions) cite{SS14}. For the special case of arithmetic progressions ($r$ collinear points that are evenly distanced) we give a bound that is tight up to low order terms, showing that a $d$-dimensional grid achieves the largest number of $r$-term progressions. The main ingredient in the proof is a new method to find a low degree polynomial that vanishes on many of the rich lines. Unlike previous applications of the polynomial method, we do not find this polynomial by interpolation. The starting observation is that the degree $r-2$ Veronese embedding takes $r$-collinear points to $r$ linearly dependent images. Hence, each collinear $r$-tuple of points, gives us a dependent $r$-tuple of images. We then use the design-matrix method of cite{BDWY12} to convert these local linear dependencies into a global one, showing that all the images lie in a hyperplane. This then translates into a low degree polynomial vanishing on the original set.
We give a fairly elementary and simple proof that shows that the number of incidences between $m$ points and $n$ lines in ${mathbb R}^3$, so that no plane contains more than $s$ lines, is $$ Oleft(m^{1/2}n^{3/4}+ m^{2/3}n^{1/3}s^{1/3} + m + nright) $$ (in the precise statement, the constant of proportionality of the first and third terms depends, in a rather weak manner, on the relation between $m$ and $n$). This bound, originally obtained by Guth and Katz~cite{GK2} as a major step in their solution of Erd{H o}ss distinct distances problem, is also a major new result in incidence geometry, an area that has picked up considerable momentum in the past six years. Its original proof uses fairly involved machinery from algebraic and differential geometry, so it is highly desirable to simplify the proof, in the interest of better understanding the geometric structure of the problem, and providing new tools for tackling similar problems. This has recently been undertaken by Guth~cite{Gu14}. The present paper presents a different and simpler derivation, with better bounds than those in cite{Gu14}, and without the restrictive assumptions made there. Our result has a potential for applications to other incidence problems in higher dimensions.
We study incidence problems involving points and curves in $R^3$. The current (and in fact only viable) approach to such problems, pioneered by Guth and Katz, requires a variety of tools from algebraic geometry, most notably (i) the polynomial partitioning technique, and (ii) the study of algebraic surfaces that are ruled by lines or, in more recent studies, by algebraic curves of some constant degree. By exploiting and refining these tools, we obtain new and improved bounds for point-curve incidence problems in $R^3$. Incidences of this kind have been considered in several previous studies, starting with Guth and Katzs work on points and lines. Our results, which are based on the work of Guth and Zahl concerning surfaces that are doubly ruled by curves, provide a grand generalization of most of the previous results. We reconstruct the bound for points and lines, and improve, in certain significant ways, recent bounds involving points and circles (in Sharir, Sheffer and Zahl), and points and arbitrary constant-degree algebraic curves (in Sharir, Sheffer and Solomon). While in these latter instances the bounds are not known (and are strongly suspected not) to be tight, our bounds are, in a certain sense, the best that can be obtained with this approach, given the current state of knowledge. As an application of our point-curve incidence bound, we show that the number of triangles spanned by a set of $n$ points in $R^3$ and similar to a given triangle is $O(n^{15/7})$, which improves the bound of Agarwal et al. Our results are also related to a study by Guth et al.~(work in progress), and have been recently applied in Sharir, Solomon and Zlydenko to related incidence problems in three dimensions.
We present a direct and fairly simple proof of the following incidence bound: Let $P$ be a set of $m$ points and $L$ a set of $n$ lines in ${mathbb R}^d$, for $dge 3$, which lie in a common algebraic two-dimensional surface of degree $D$ that does not contain any 2-flat, so that no 2-flat contains more than $s le D$ lines of $L$. Then the number of incidences between $P$ and $L$ is $$ I(P,L)=Oleft(m^{1/2}n^{1/2}D^{1/2} + m^{2/3}min{n,D^{2}}^{1/3}s^{1/3} + m + nright). $$ When $d=3$, this improves the bound of Guth and Katz~cite{GK2} for this special case, when $D$ is not too large. A supplementary feature of this work is a review, with detailed proofs, of several basic (and folklore) properties of ruled surfaces in three dimensions.
We show that the maximum number of pairwise non-overlapping $k$-rich lenses (lenses formed by at least $k$ circles) in an arrangement of $n$ circles in the plane is $Oleft(frac{n^{3/2}log{(n/k^3)}}{k^{5/2}} + frac{n}{k} right)$, and the sum of the degrees of the lenses of such a family (where the degree of a lens is the number of circles that form it) is $Oleft(frac{n^{3/2}log{(n/k^3)}}{k^{3/2}} + nright)$. Two independent proofs of these bounds are given, each interesting in its own right (so we believe). We then show that these bounds lead to the known bound of Agarwal et al. (JACM 2004) and Marcus and Tardos (JCTA 2006) on the number of point-circle incidences in the plane. Extensions to families of more general algebraic curves and some other related problems are also considered.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
