Subquadratic Algorithms for Some textsc{3Sum}-Hard Geometric Problems in the Algebraic Decision Tree Model

We present subquadratic algorithms in the algebraic decision-tree model for several textsc{3Sum}-hard geometric problems, all of which can be reduced to the following question: Given two sets $A$, $B$, each consisting of $n$ pairwise disjoint segments in the plane, and a set $C$ of $n$ triangles in the plane, we want to count, for each triangle $Deltain C$, the number of intersection points between the segments of $A$ and those of $B$ that lie in $Delta$. The problems considered in this paper have been studied by Chan~(2020), who gave algorithms that solve them, in the standard real-RAM model, in $O((n^2/log^2n)log^{O(1)}log n)$ time. We present solutions in the algebraic decision-tree model whose cost is $O(n^{60/31+varepsilon})$, for any $varepsilon>0$. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl~(2020). A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the emph{order type} of the lines, a handicap that turns out to be beneficial for speeding up our algorithm.

On Ray Shooting for Triangles in 3-Space and Related Problems

We consider several problems that involve lines in three dimensions, and present improved algorithms for solving them. The problems include (i) ray shooting amid triangles in $R^3$, (ii) reporting intersections between query lines (segments, or rays) and input triangles, as well as approximately counting the number of such intersections, (iii) computing the intersection of two nonconvex polyhedra, (iv) detecting, counting, or reporting intersections in a set of lines in $R^3$, and (v) output-sensitive construction of an arrangement of triangles in three dimensions. Our approach is based on the polynomial partitioning technique. For example, our ray-shooting algorithm processes a set of $n$ triangles in $R^3$ into a data structure for answering ray shooting queries amid the given triangles, which uses $O(n^{3/2+varepsilon})$ storage and preprocessing, and answers a query in $O(n^{1/2+varepsilon})$ time, for any $varepsilon>0$. This is a significant improvement over known results, obtained more than 25 years ago, in which, with this amount of storage, the query time bound is roughly $n^{5/8}$. The algorithms for the other problems have similar performance bounds, with similar improvements over previous results. We also derive a nontrivial improved tradeoff between storage and query time. Using it, we obtain algorithms that answer $m$ queries on $n$ objects in [ max left{ O(m^{2/3}n^{5/6+varepsilon} + n^{1+varepsilon}),; O(m^{5/6+varepsilon}n^{2/3} + m^{1+varepsilon}) right} ] time, for any $varepsilon>0$, again an improvement over the earlier bounds.

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

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.

On rich lenses in planar arrangements of circles and related problems

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.

Incidences with curves in three 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.

On Radial Isotropic Position: Theory and Algorithms

We review the theory of, and develop algorithms for transforming a finite point set in ${bf R}^d$ into a set in emph{radial isotropic position} by a nonsingular linear transformation followed by rescaling each image point to the unit sphere. This problem arises in a wide spectrum of applications in computer science and mathematics. Our algorithms use gradient descent methods for a particular convex function $f$ whose minimum defines the transformation, and our main focus is on analyzing their performance. Although the minimum can be computed exactly, by expensive symbolic algebra techniques, gradient descent only approximates the desired minimum to any desired level of accuracy. We show that computing the gradient of $f$ amounts to computing the Singular Value Decomposition (SVD) of a certain matrix associated with the input set, making it simple to implement. We believe it to be superior to other approximate techniques (mainly the ellipsoid algorithm) used previously to find this transformation, and it should run much faster in practice. We prove that $f$ is smooth, which yields convergence rate proportional to $1/epsilon$, where $epsilon$ is the desired approximation accuracy. To complete the analysis, we provide upper bounds on the norm of the optimal solution which depend on new parameters measuring the degeneracy in our input. We believe that our parameters capture degeneracy better than other, seemingly weaker, parameters used in previous works. We next analyze the strong convexity of $f$, and present two worst-case lower bounds on the smallest eigenvalue of its Hessian. This gives another worst-case bound on the convergence rate of another variant of gradient decent that depends only logarithmically on $1/epsilon$.

Incidences between points and curves with almost two degrees of freedom

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.

Distinct distances between a collinear set and an arbitrary set of points

We consider the number of distinct distances between two finite sets of points in ${bf R}^k$, for any constant dimension $kge 2$, where one set $P_1$ consists of $n$ points on a line $l$, and the other set $P_2$ consists of $m$ arbitrary points, such that no hyperplane orthogonal to $l$ and no hypercylinder having $l$ as its axis contains more than $O(1)$ points of $P_2$. The number of distinct distances between $P_1$ and $P_2$ is then $$ Omegaleft(minleft{ n^{2/3}m^{2/3},; frac{n^{10/11}m^{4/11}}{log^{2/11}m},; n^2,; m^2right}right) . $$ Without the assumption on $P_2$, there exist sets $P_1$, $P_2$ as above, with only $O(m+n)$ distinct distances between them.

Incidences between points and lines on a two-dimensional variety

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.

Incidences between points and lines in three dimensions

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.