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 ${\mathbb{R}}^k$, for any constant dimension $k\ge 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\left(1\right)$ points of $P_2$. The number of distinct distances between $P_1$ and $P_2$ is then

$\Omega \left(min\left\{n^{2∕3}{m}^{2∕3},\frac{n^{10∕11}{m}^{4∕11}}{{log}^{2∕11}m},n^2,m^2\right\}\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.     

Extremal problems on triangle areas in two and three dimensions

The study of extremal problems on triangle areas was initiated in a series of papers by Erd?s and Purdy in the early 1970s. In this paper we present new results on such problems, concerning the number of triangles of the same area that are spanned by finite point sets in the plane and in 3-space, and the number of distinct areas determined by the triangles.In the plane, our main result is an O(n44/19)=O(n^2.3158) upper bound on the number of unit-area triangles spanned by n points, which is the first breakthrough improving the classical bound of O(n7/3) from 1992. We also make progress in a number of important special cases. We show that: (i) For points in convex position, there exist n-element point sets that span Ω(nlogn) triangles of unit area. (ii) The number of triangles of minimum (nonzero) area determined by n points is at most ; there exist n-element point sets (for arbitrarily large n) that span (6/π²−o(1))n² minimum-area triangles. (iii) The number of acute triangles of minimum area determined by n points is O(n); this is asymptotically tight. (iv) For n points in convex position, the number of triangles of minimum area is O(n); this is asymptotically tight. (v) If no three points are allowed to be collinear, there are n-element point sets that span Ω(nlogn) minimum-area triangles (in contrast to (ii), where collinearities are allowed and a quadratic lower bound holds).In 3-space we prove an O(n17/7β(n))=O(n^2.4286) upper bound on the number of unit-area triangles spanned by n points, where β(n) is an extremely slowly growing function related to the inverse Ackermann function. The best previous bound, O(n8/3), is an old result of Erd?s and Purdy from 1971. We further show, for point sets in 3-space: (i) The number of minimum nonzero area triangles is at most n²+O(n), and this is worst-case optimal, up to a constant factor. (ii) There are n-element point sets that span Ω(n4/3) triangles of maximum area, all incident to a common point. In any n-element point set, the maximum number of maximum-area triangles incident to a common point is O(n4/3+ε), for any ε>0. (iii) Every set of n points, not all on a line, determines at least Ω(n2/3/β(n)) triangles of distinct areas, which share a common side.     

Degenerate Crossing Numbers

Let G be a graph with n vertices and e≥4n edges, drawn in the plane in such a way that if two or more edges (arcs) share an interior point p, then they properly cross one another at p. It is shown that the number of crossing points, counted without multiplicity, is at least constant times e and that the order of magnitude of this bound cannot be improved. If, in addition, two edges are allowed to cross only at most once, then the number of crossing points must exceed constant times (e/n)⁴. The research of J. Pach was supported by NSF grant CCF-05-14079 and by grants from NSA, PSC-CUNY, BSF, and OTKA-K-60427. The research of G. Tóth was supported by OTKA-K-60427.     

Homotheties and incidences

We consider problems involving rich homotheties in a set $S$ of $n$ points in the plane (that is, homotheties that map many points of $S$ to other points of $S$). By reducing these problems to incidence problems involving points and lines in ${\mathbb{R}}^3$, we are able to obtain refined and new bounds for the number of rich homotheties, and for the number of distinct equivalence classes, under homotheties, of $k$-element subsets of $S$, for any $k\ge 3$. We also discuss the extensions of these problems to three and higher dimensions.     

On lines, joints, and incidences in three dimensions

We extend (and somewhat simplify) the algebraic proof technique of Guth and Katz (2010) [9], to obtain several sharp bounds on the number of incidences between lines and points in three dimensions. Specifically, we show: (i) The maximum possible number of incidences between n lines in R³ and m of their joints (points incident to at least three non-coplanar lines) is Θ(m1/3n) for m?n, and Θ(m2/3n2/3+m+n) for m?n. (ii) In particular, the number of such incidences cannot exceed O(n3/2). (iii) The bound in (i) also holds for incidences between n lines and m arbitrary points (not necessarily joints), provided that no plane contains more than O(n) points and each point is incident to at least three lines. As a preliminary step, we give a simpler proof of (an extension of) the bound O(n3/2), established by Guth and Katz, on the number of joints in a set of n lines in R³. We also present some further extensions of these bounds, and give a trivial proof of Bourgain's conjecture on incidences between points and lines in 3-space, which is an immediate consequence of our incidence bounds, and which constitutes a much simpler alternative to the proof of Guth and Katz (2010) [9].     

Szemerédi–Trotter-type theorems in dimension 3

We estimate the number of incidences in a configuration of m lines and n   points in dimension 3. The main term is mn^1/3$m{n}^{1/3}$ if we work over the real or complex numbers but mn^2/5$m{n}^{2/5}$ over finite fields.     

Threshold functions for incidence properties in finite vector spaces

The main purpose of this paper is to provide threshold functions for the events that a random subset of the points of a finite vector space has certain properties related to point-flat incidences. Specifically, we consider the events that there is an ℓ-rich m-flat with regard to a random set of points in ${\mathbb{F}}_q^n$, the event that a random set of points is an m-blocking set, and the event that there is an incidence between a random set of points and a random set of m-flats. One of our key ingredients is a stronger version of a recent result obtained by Chen and Greenhill (2021).