Distinct Distances with $\ell_{p}$ Metrics

We adapt Székely’s proof [16] for Euclidean metric. We may assume that $p\geq 3$, since the case of $p=2$ was handled in [15]. Set $t=\max_{u\in\mathcal{P}}D(u,\mathcal{P})$. In other words, $t$ is the maximum number of distances between a point of $\mathcal{P}$ and the rest of $\mathcal{P}$. We may assume that $t=O(n/\log^{2}n)$, since otherwise we are done.

Throughout the proof, when mentioning circles, we refer to circles defined by the $\ell_{p}$ norm (rather than to Euclidean circles). That is, the set of points at a given distance from a given point. Let $\mathcal{C}$ be the set of circles centered at a point of $\mathcal{P}$ and incident to another point of $\mathcal{P}$. By definition, each point of $\mathcal{P}$ has at most $t$ such circles centered at it. This implies that $|\mathcal{C}|\leq nt$. Since each point of $\mathcal{P}$ is incident to a circle centered at every other point, we have that $I(\mathcal{P},\mathcal{C})=n(n-1)$. We remove from $\mathcal{C}$ all circles incident to at most two points of $\mathcal{P}$. This decreases the number of incidences by at most $2nt$, so we still have that $I(\mathcal{P},\mathcal{C})=\Theta(n^{2})$.

Consider the graph $G=(V,E)$, defined as follows. The set $V$ contains a vertex for each point of $\mathcal{P}$. For every circle $\gamma\in\mathcal{C}$, we add to $E$ an edge between every two points that are consecutive along $\gamma$. Note that pairs of points that are consecutive in multiple circles of $\mathcal{C}$ lead to parallel edges in $G$. The proof proceeds by double counting $\mathrm{cr}(G)$.

We draw every vertex of $V$ as its corresponding point and every edge of $E$ as the corresponding circular arc from $\mathcal{C}$. In this drawing, edges intersect only at the intersection points of the circles of $\mathcal{C}$. Two circles have at most two intersection points (for example, see [8, Lemma 1.4]). This implies

A circle of $\mathcal{C}$ that is incident to $j\geq 3$ points of $\mathcal{P}$ contributes $j$ edges to $E$. Since $I(\mathcal{P},\mathcal{C})=\Theta(n^{2})$, we get that $|E|=\Theta(n^{2})$. To get a lower bound for $\mathrm{cr}(G)$, we wish to rely on Lemma 2.3. However, since some edges in $E$ may have a high multiplicity, this leads to a weak bound. Thus, we first study edges with high multiplicity.

Consider distinct points $u,v\in\mathcal{P}$. Every edge in $E$ between $u$ and $v$ corresponds to a distinct point of $\mathcal{P}$ that is equidistant from $u$ and $v$. In other words, every edge between $u$ and $v$ corresponds to a point of $\mathcal{P}$ that is incident to $\mathcal{B}(u,v)$. Thus, edges with high multiplicity correspond to bisectors that contain many points of $\mathcal{P}$. For $k$ whose value will be determined below, we study edges with multiplicity at least $k$. We separately handle bisectors that are lines and other bisectors.

Let $T_{j}\subset\mathcal{P}^{3}$ be the set of triples $(u,v,w)$ where the multiplicity of the edge $(u,v)$ is at least $k$, the bisector $\mathcal{B}(u,v)$ is $2^{j}$-rich, and $w\in\mathcal{B}(u,v)$. Note that every such triple corresponds to at least $2^{j}$ edges with multiplicity at least $k$. We now derive an upper bound for $|T_{j}|$.

Let $\ell$ be a $2^{j}$-rich line with one of the four aforementioned slopes. Let $w\in\mathcal{P}$ be a point incident to $\ell$. Since the circles of the $\ell_{p}$ metric are strictly convex, every circle centered at $w$ intersects $\ell$ twice. By definition, at most $t$ such circles are incident to points of $\mathcal{P}$. Each circle contains at most two pairs $(u,v)\in\mathcal{P}^{2}$ that are consecutive along the circle and satisfy $\ell=\mathcal{B}(u,v)$. We conclude that $|T_{j}|=O(tn/k)$.

We partition the edges of $E$ according to their multiplicity. Specifically, for each $\log k\leq j\leq\log n$, we consider edges with multiplicity at least $2^{j}$ and smaller than $2^{j+1}$. This implies that the number of edges with a line bisector and multiplicity at least $k$ is smaller than

We remove the above edges. The assumption $t=O(n/\log^{2}n)$ implies that the number of removed edges is $O(n^{2}/\log n)$. We thus still have that $|E|=\Theta(n^{2})$.

Since every curve of $\Gamma$ is incident to at least $2^{j}$ points of $\mathcal{P}$, we have that $I(\mathcal{P},\Gamma)\geq 2^{j}|\Gamma|$. Combining this with the above upper bound and setting ${\varepsilon}^{\prime\prime}=32{\varepsilon}^{\prime}/(1-8{\varepsilon}^{\prime})$ yields

(Since $j$ is assumed to be sufficiently large, the fourth term in (3) cannot dominate the bound.)

The first term on the right-hand side of (4) dominates the bound when $2^{j}=O(n^{(2+{\varepsilon}^{\prime\prime})/5})$. The second term of (4) dominates when $2^{j}=\Omega(n^{(2+{\varepsilon}^{\prime\prime})/5})$ and $2^{j}=O(\sqrt{n})$. The last term of (4) dominates when $2^{j}=\Omega(\sqrt{n})$. As in the case of line bisectors, we dyadically decompose the edges of $E$ according to their multiplicity. In this case, each bisector corresponds to at most one pair $(u,v)\in\mathcal{P}^{2}$. Thus, the number of edges with a non-line bisector and multiplicity at least $k$ is

Taking $k=C_{p,{\varepsilon}^{\prime}}n^{(2+{\varepsilon}^{\prime\prime})/7}$, for an appropriate constant $C_{p,{\varepsilon}^{\prime}}$, leads to at most $n^{2}/100$ edges with multiplicity at least $k$ and a non-line bisector. As in the line bisector case, We remove those edges, while still having that $|E|=\Theta(n^{2})$.

Combining this with (2) leads to $n^{\frac{26-{\varepsilon}^{\prime\prime}}{7}}=O(n^{2}t^{2})$. Simplifying gives $t=\Omega\left(n^{\frac{6}{7}-\frac{{\varepsilon}^{\prime\prime}}{14}}\right)$. To complete the theorem, we choose ${\varepsilon}^{\prime}$ such that ${\varepsilon}={\varepsilon}^{\prime\prime}/14$.

We wish to apply Theorem 2.4, but we have segments of algebraic curves rather than algebraic curves. We thus replace each segment with the algebraic curve that contains it.³³3More formally, we take the Zariski closure of each segment. This leads to a new potential issue: Segments originating from different bisectors may be contained in the same irreducible algebraic curve.

From (1), the curves that contain the segments are all of the form

where $a_{1},a_{2},a_{3},a_{4}\in\mathbb{R}$. Each $\pm$ symbol may represent a different sign.

By Lemma 2.2, every bisector segment is either unbounded or contains an inflection point. By inspecting (5), we note that such a curve may contain at most four unbounded segments. Indeed, unbounded segments may only occur when $x,y\to\pm\infty$.

Recall that inflection points occur when $\frac{\partial^{2}}{\partial^{2}x}y=0$ and when $\frac{\partial^{2}}{\partial^{2}y}x=0$. We now study the former, and the latter can be handled symmetrically. We take a derivative of (5) according to $x$ and rearrange, obtaining

Taking another derivative leads to

where $f\in\mathbb{R}[x,y]$ is of degree smaller than $3p$.

The inflection points of the curve are the solutions to (5) that also satisfy $f(x,y)=0$. Note that (5) and the set of solutions to $f(x,y)=0$ cannot share irreducible components, since no non-line irreducible curve consists entirely of inflection points. By Bézout’s theorem (for example, see [3]), there are fewer than $3p^{2}$ solutions to this system. Including also four unbounded segments and derivatives according to $y$, the number of bisector segments contained in a curve of the form (5) is smaller than $6p^{2}+4$.

We apply Theorem 2.4 while keeping one copy of each curve that repeats multiple times. To obtain a valid upper bound for the number of incidences, we multiply the bound of the theorem by $6p^{2}+4$. The rest of the proof is identical to that of the even case. ∎

(a) Let $(x_{1},y_{1})$ be the point of $\mathcal{P}$ that minimizes the value of $x+y$. Let $(x_{2},y_{2})$ be the point that maximizes this value. Set $I_{1}^{+}=x_{1}+y_{1}$ and $I_{4}^{+}=x_{2}+y_{2}$. The meaning of this notation will become clear below. For now, note that each $I^{+}$ can be thought of as the projection of a point on the line $y=-x$. There might be multiple points satisfying $x+y=I_{1}^{+}$ and $x+y=I_{4}^{+}$. Among those, we choose $(x_{1},y_{1})$ and $(x_{2},y_{2})$ that minimize $(y_{1}-x_{1})-(y_{2}-x_{2})$. Let $(x_{3},y_{3})$ be the point of $\mathcal{P}$ that minimizes the value of $y-x$. Let $(x_{4},y_{4})$ be the point that maximizes this value. Set $I_{1}^{-}=y_{3}-x_{3}$ and $I_{4}^{-}=y_{4}-x_{4}$. When there are multiple points that lead to these values, We choose $(x_{3},y_{3})$ and $(x_{4},y_{4})$ that minimize $(x_{3}+y_{3})-(x_{4}+y_{4})$.

By definition, $\mathcal{P}$ is contained in the rectangle $R$ defined by $I_{1}^{+}\leq x+y\leq I_{4}^{+}$ and $I_{1}^{-}\leq y-x\leq I_{4}^{-}$. We cut $R$ into at most nine rectangular pieces using:

• •

  The line of slope 1 incident to $(x_{1},y_{1})$.

• •

  The line of slope 1 incident to $(x_{2},y_{2})$.

• •

  The line of slope -1 incident to $(x_{3},y_{3})$.

• •

  The line of slope -1 incident to $(x_{4},y_{4})$.

An example is depicted in Figure 2. There are fewer than nine rectangles when two of the lines are identical or when a line contains a side of $R$.

Set $\mathcal{P}^{\prime}=\{(x_{1},y_{1}),(x_{2},y_{2}),(x_{3},y_{3}),(x_{4},y_{4})\}$. These four points are not necessarily distinct. If a point appears more than once in $\mathcal{P}^{\prime}$, then we only keep one copy of that point. That is, $\mathcal{P}^{\prime}$ is a set of at most four distinct points.

We consider the case where $y_{1}-x_{1}\geq y_{2}-x_{2}$. The case where $y_{1}-x_{1}<y_{2}-x_{2}$ can be handled symmetrically. We set $I_{3}^{-}=y_{1}-x_{1}$ and $I_{2}^{-}=y_{2}-x_{2}$. Note that $I_{1}^{-}\leq I_{2}^{-}\leq I_{3}^{-}\leq I_{4}^{-}$. The analysis of the case of $y_{1}-x_{1}\geq y_{2}-x_{2}$ is further divided into two cases, as follows.

Figure 2 depicts Case 1 when there are nine distinct rectangles.

Consider a point $u\in\mathcal{P}^{\prime}$. Since $D(\mathcal{P})=\Theta(\sqrt{n})$, the points of $\mathcal{P}\setminus\{u\}$ are contained in a set ${\mathcal{Q}}_{u}$ of $O(\sqrt{n})$ axis-parallel squares centered at $u$. By the pigeonhole principle, there exists a square in ${\mathcal{Q}}_{u}$ that contains at least $n/|{\mathcal{Q}}_{p}|$ points of $\mathcal{P}$. It is not difficult to check that these points span $\Omega(n/|{\mathcal{Q}}_{u}|)$ distinct distances. Since $D(\mathcal{P})=\Theta(\sqrt{n})$, we get that $|{\mathcal{Q}}_{u}|=\Omega(\sqrt{n})$. That is, $|{\mathcal{Q}}_{u}|=\Theta(\sqrt{n})$.