Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIncidences between points and lines in three dimensions
195
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
We study incidences between points and algebraic curves in three dimensions, taken from a family $C$ of curves that have almost two degrees of freedom, meaning that every pair of curves intersect in $O(1)$ points, for any pair of points $p$, $q$, there are only $O(1)$ curves of $C$ that pass through both points, and a pair $p$, $q$ of points admit a curve of $C$ that passes through both of them iff $F(p,q)=0$ for some polynomial $F$. We study two specific instances, one involving unit circles in $R^3$ that pass through some fixed point (so called anchored unit circles), and the other involving tangencies between directed points (points and directions) and circles in the plane; a directed point is tangent to a circle if the point lies on the circle and the direction is the tangent direction. A lifting transformation of Ellenberg et al. maps these tangencies to incidences between points and curves in three dimensions. In both instances the curves in $R^3$ have almost two degrees of freedom. We show that the number of incidences between $m$ points and $n$ anchored unit circles in $R^3$, as well as the number of tangencies between $m$ directed points and $n$ arbitrary circles in the plane, is $O(m^{3/5}n^{3/5}+m+n)$. We derive a similar incidence bound, with a few additional terms, for more general families of curves in $R^3$ with almost two degrees of freedom. The proofs follow standard techniques, based on polynomial partitioning, but face a novel issue involving surfaces that are infinitely ruled by the respective family of curves, as well as surfaces in a dual 3D space that are infinitely ruled by the respective family of suitably defined dual curves. The general bound that we obtain is $O(m^{3/5}n^{3/5}+m+n)$ plus additional terms that depend on how many curves or dual curves can lie on an infinitely-ruled surface.
By bootstrap percolation we mean the following deterministic process on a graph $G$. Given a set $A$ of vertices infected at time 0, new vertices are subsequently infected, at each time step, if they have at least $rinmathbb{N}$ previously infected neighbors. When the set $A$ is chosen at random, the main aim is to determine the critical probability $p_c(G,r)$ at which percolation (infection of the entire graph) becomes likely to occur. This bootstrap process has been extensively studied on the $d$-dimensional grid $[n]^d$: with $2leq rleq d$ fixed, it was proved by Cerf and Cirillo (for $d=r=3$), and by Cerf and Manzo (in general), that [p_c([n]^d,r)=Thetabiggl(frac{1}{log_{(r-1)}n}biggr)^{d-r+1},] where $log_{(r)}$ is an $r$-times iterated logarithm. However, the exact threshold function is only known in the case $d=r=2$, where it was shown by Holroyd to be $(1+o(1))frac{pi^2}{18log n}$. In this paper we shall determine the exact threshold in the crucial case $d=r=3$, and lay the groundwork for solving the problem for all fixed $d$ and $r$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
