Tight Bounds on the Number of Closest Pairs in Vertical Slabs

We write $\mathrm{\ell }$ for the vertical line. We define a graph, $G^{+}$, with vertex set $S$. Each segment of $𝒞𝒫$ with a positive slope represents an edge in the graph $G^{+}$. Let $F$ be the subgraph of $G^{+}$ induced by the segments of $𝒞𝒫$ that cross $\mathrm{\ell }$. We will show that $F$ does not contain a cycle.

Suppose, to the contrary, that there is a cycle $C$ in $F$. Let $a$ and $b$ be the endpoints of the shortest edge in $C$ such that $a$ is to the left of $\mathrm{\ell }$ and $b$ is to the right of $\mathrm{\ell }$. Let $ac$ and $bd$ be the other edges of the cycle that are incident to $a$ and $b$, respectively. Since both $ab$ and $ac$ represent pairs in $𝒞𝒫$ and both have a positive slope, we have and . Similarly, we have and ; see Figure 1.

Let $c^{\prime }$ be the reflection of the point $c$ with respect to the horizontal line through $b$. Note that $\Vert b-c^{\prime }\Vert =\Vert b-c\Vert >\Vert b-d\Vert$, because $bd$ represents a pair in $A(S,n)$ and the vertical slab $⟦b_x,d_x⟧$ contains the point $c$. Since $\Vert b-c^{\prime }\Vert >\Vert b-d\Vert$, we have . We also have and . It follows that .

Consider the bisector of the segment $c{c}^{\prime }$ (which is the horizontal line through $b$). Observe that the point $a$ is located on the same side as $c^{\prime }$ with respect to this bisector. Therefore, . Combined with , this implies that . This contradicts the facts that $ac$ represents a pair in $A(S,n)$ and the point $d$ is in the slab $⟦a_x,c_x⟧$.

A similar argument shows that the segments in $𝒞𝒫$ that cross $\mathrm{\ell }$ and have negative slopes do not contain a cycle. Therefore, the total number of segments in $𝒞𝒫$ that cross the line $\mathrm{\ell }$ is $O(n)$. $◀$

To prove Lemma 3 for dimensions $d\ge 2$, we will use the Well-Separated Pair Decomposition (WSPD), as introduced by Callahan and Kosaraju [2]. Let $S$ be a set of $n$ points in ${ℝ}^d$ and let $s>1$ be a real number, called the separation ratio. A WSPD for $S$ is a set of pairs $\{A_i,B_i\}$, for $i=1,2,\mathrm{\dots },k$, for some positive integer $k$, such that

1. 1.

   for each $i$, $A_i\subseteq S$ and $B_i\subseteq S$,

2. 2.

   for each $i$, there exist two balls $D$ and $D^{\prime }$ of the same radius, say $\rho$, such that $A_i\subseteq D$, $B_i\subseteq D^{\prime }$, and the distance between $D$ and $D^{\prime }$ is at least $s\cdot \rho$, i.e., the distance between their centers is at least $(s+2)\cdot \rho$,

3. 3.

   for any two distinct points $p$ and $q$ in $S$, there is a unique index $i$ such that $p\in A_i$ and $q\in B_i$ or vice-versa.

Consider a pair $\{A_i,B_i\}$ in a WSPD. If $p$ and $p^{\prime }$ are two points in $A_i$ and $q$ is a point in $B_i$, then it is easy to see that

Let $s>2$ be a constant and consider a WSPD $\{A_i,B_i\}$, $i=1,2,\mathrm{\dots },k$, for the point set $S$ with separation ratio $s$, where $k=O(n)$; see Lemma 4. We define the following geometric graph $G$ on the point set $S$. For each $i$ with $1\le i\le k$, let

• $\mathrm{■}$

  $a_i$ be the rightmost point in $A_i$ that is to the left of $H$,

• $\mathrm{■}$

  $b_i$ be the leftmost point in $B_i$ that is to the right of $H$,

• $\mathrm{■}$

  $a_i^{\prime }$ be the leftmost point in $A_i$ that is to the right of $H$, and

• $\mathrm{■}$

  $b_i^{\prime }$ be the rightmost point in $B_i$ that is to the left of $H$.

We add the edges $a_i{b}_i$ and $a_i^{\prime }{b}_i^{\prime }$ to the graph $G$. Note that some of these points may not exist, in which case we ignore the corresponding edge. It is clear that $G$ has $O(n)$ edges. The lemma will follow from the fact that every segment in $𝒞𝒫$ that crosses $H$ is an edge in $G$.

Let $pq$ be a pair in $𝒞𝒫$ that crosses $H$, and let $Q$ be a vertical slab such that $pq$ is the closest pair in $Q\cap S$. We may assume, without loss of generality, that $p$ is to the left of $H$ and $q$ is to the right of $H$. Let $i$ be the index such that (i) $p\in A_i$ and $q\in B_i$ or (ii) $p\in B_i$ and $q\in A_i$. We may assume, without loss of generality, that (i) holds.

We claim that $p=a_i$. To prove this, suppose that $p\ne a_i$. Then, since $p$ is to the left of $a_i$, $a_i$ is in the slab $Q$. Since $s>2$, Equation (1) yields , which is a contradiction. By a symmetric argument, we have $q=b_i$. Thus, $pq$ is an edge in $G$. $◀$

Lemma 3 gives us a divide-and-conquer approach to prove an upper bound on $f_d(n,m)$:

Let $S$ be a set of $n$ points in ${ℝ}^d$ for which $f_d(n,m)=|A(S,m)|$. Let be real numbers such that for each $i=1,2,\mathrm{\dots },m$, there are exactly $n/m$ points in $S$ that are strictly inside the vertical slab $⟦H_{a_i},H_{a_{i+1}}⟧$.

Let $H=H_{a_{1+m/2}}$. Observe that $n/2$ points of $S$ are to the left of $H$ and $n/2$ points of $S$ are to the right of $H$. Denote these two subsets by $S^{-}$ and $S^{+}$, respectively. Each pair in $A(S,m)$ is either a pair in $A(S^{-},m/2)$ or a pair in $A(S^{+},m/2)$ or it crosses $H$. Using Lemma 3, it follows that

If we apply this recurrence $k$ times, we get

For $k=\log (m^2/n)$, we have $n/2^k=n^2/m^2$ and $m/2^k=n/m$. Thus,

Since $f_d(n^2/m^2,n/m)=O(n^2/m^2)$, we conclude that

$◀$

It is clear that $f_2(n,m)\le \left(\genfrac{}{}{0pt}{}{m+1}{2}\right)$. To prove the lower bound, we will construct a set $S$ of $n$ points in ${ℝ}^2$ such that the $\left(\genfrac{}{}{0pt}{}{m+1}{2}\right)$ vertical slabs have distinct closest pairs.

For $i=1,2,\mathrm{\dots },m+1$, we take $a_i=i$ and consider the corresponding hyperplane $H_i$. Let be the set of all possible vertical slabs. We define the size of a slab $⟦H_i,H_j⟧$ to be the difference $j-i$ of their indices.

We start by constructing a set $P$ of $m(m+1)$ points such that the slabs in $𝒬$ contain distinct closest pairs in $P$, and for each $i=1,2,\mathrm{\dots },m$, the slab $⟦H_i,H_{i+1}⟧$ contains exactly $m+1$ points of $P$.

Note that the slab $⟦H_1,H_{m+1}⟧$ has the largest size. Let $p$ be an arbitrary point in $⟦H_1,H_2⟧$ and let $q$ be an arbitrary point in $⟦H_m,H_{m+1}⟧$. We initialize $P=\{p,q\}$, $D=\Vert p-q\Vert$, and delete the slab $⟦H_1,H_{m+1}⟧$ from $𝒬$.

As long as $𝒬$ is non-empty, we do the following:

• $\mathrm{■}$

  Take a slab $⟦H_i,H_j⟧$ of largest size in $𝒬$.

• $\mathrm{■}$

  Let $p$ be an arbitrary point in $⟦H_i,H_{i+1}⟧$ such that $p$ is above the bounding box of $P$, and the distance between $p$ and any point in $P$ is more than $D+2$.

• $\mathrm{■}$

  Let $q$ be an arbitrary point in $⟦H_{j-1},H_j⟧$ such that $q$ is above the bounding box of $P$, the distance between $q$ and any point in $P$ is more than $D+2$, and $\Vert p-q\Vert =D+1$.

• $\mathrm{■}$

  Add $p$ and $q$ to $P$.

• $\mathrm{■}$

  Set $D=\Vert p-q\Vert$.

• $\mathrm{■}$

  Delete the slab $⟦H_i,H_j⟧$ from $𝒬$.

It is not difficult to see that the final point set $P$ has the properties stated above.

To obtain the final point set $S$, of size $n$, we define a set $P^{\prime }$ of $n-m(m+1)$ points, such that each point in $P^{\prime }$ has distance more than $D$ to all points of $P$, the closest pair distance in $P^{\prime }$ is more than $D$, and for each $i=1,2,\mathrm{\dots },m$, the slab $⟦H_i,H_{i+1}⟧$ contains $n/m-(m-1)$ points of $P^{\prime }$. The point set $S=P\cup P^{\prime }$ has the property that $|A(S,m)|=\left(\genfrac{}{}{0pt}{}{m+1}{2}\right)$. $◀$

For $i=1,2,\mathrm{\dots },m+1$, we take $a_i=i$ and consider the corresponding hyperplane $H_i$.

Let $m^{\prime }=\sqrt{n}/4$ and $n^{\prime }=m^{\prime }(m^{\prime }+1)$. We apply Theorem 6, where we replace $n$ by $n^{\prime }$ and $m$ by $m^{\prime }$. This gives us a set $S^{\prime }$ of $n^{\prime }$ points with $|A(S^{\prime },m^{\prime })|=f_2(n^{\prime },m^{\prime })$. The points of $S^{\prime }$ are between the hyperplanes $H_1$ and $H_{m^{\prime }+1}$; for each $i=1,2,\mathrm{\dots },m^{\prime }$, the vertical slab $⟦H_i,H_{i+1}⟧$ contains $n^{\prime }/m^{\prime }$ points of $S^{\prime }$. Note that

Let $D$ be the diameter of $S^{\prime }$. Let $S$ be the union of $S^{\prime }$ and a set of $n-n^{\prime }$ additional points that have pairwise distances more than $D$, whose distances to the points in $S^{\prime }$ are more than $D$, and such that for each $i=1,2,\mathrm{\dots },m$, the vertical slab $⟦H_i,H_{i+1}⟧$ contains $n/m$ points of $S$. It is clear that

Note that this construction is possible, because (i) , (ii) , and (iii) ; these inequalities follow by straightforward algebraic manipulations, using the assumptions on $n$ and $m$ in the statement of the corollary. Finally, these assumptions imply that $m^{\prime }\ge m/12$. We conclude that $f_2(n,m)=\mathrm{\Omega }(m^2)$. $◀$

Before we prove the lower bound for the remaining case, i.e., $m>3\sqrt{n}$, we consider the case when $m=n$, which will serve as a warm up.

We assume for simplicity that $n$ is a sufficiently large power of two. We will construct a point set $S$ of size $n$ for which $|A(S,n)|=\mathrm{\Omega }(n\log n)$.

Let $k=\log n$. For $i=0,1,\mathrm{\dots },k-1$, let $x_i=2^i$ and let $v_i=(x_i,y_i)$ be a vector, where the value of $y_i$ is inductively defined as follows: We set $y_{k-1}=0$. Assuming that $y_{k-1},y_{k-2},\mathrm{\dots },y_{i+1}$ have been defined, we set $y_i$ to an integer such that

We define

Note that each binary sequence of length $k$ represents a unique point in $S$. Using this representation, each point of $S$ corresponds to a vertex of a $k$-dimensional hypercube $Q_k$. We will prove below that each edge of $Q_k$ corresponds to a closest pair in a unique vertical slab. Since $Q_k$ has $k\cdot 2^{k-1}=\mathrm{\Omega }(n\log n)$ edges, this will complete the proof.

Consider an arbitrary edge of $Q_k$. The two vertices of this edge are binary sequences of length $k$ that have Hamming distance one, i.e., they differ in exactly one bit. Let $t$ be the position at which they differ. Observe that $0\le t\le k-1$. Let $r$ and $s$ be the points of $S$ that correspond to the two vertices of this edge. Then $v_t$ is either $r-s$ or $s-r$. We will prove that $r$ and $s$ form the closest pair in the vertical slab $⟦H_{r_1},H_{s_1}⟧$, where $r_1$ and $s_1$ are the first coordinates of $r$ and $s$, respectively (assuming that ). Note that $r_1$ and $s_1$ are integers.

Let $p$ and $q$ be two points in $⟦H_{r_1},H_{s_1}⟧\cap S$ such that $\{p,q\}\ne \{r,s\}$. We have to show that . Since $p$ and $q$ are points in $S$, we can write them as

Let $\mathrm{\ell }$ be the smallest index for which ${\beta }_{p,\mathrm{\ell }}\ne {\beta }_{q,\mathrm{\ell }}$. Then

By the triangle inequality, we have $\Vert a+b\Vert \le \Vert a\Vert +\Vert b\Vert$ and $\Vert a+b\Vert \ge \Vert a\Vert -\Vert b\Vert$ for any two vectors $a$ and $b$. These two inequalities, together with (2), imply that

Thus, it suffices to show that $\Vert v_{\mathrm{\ell }}\Vert \ge 2\cdot \Vert r-s\Vert =2\cdot \Vert v_t\Vert$. If we can show that , then, using (2),

and the proof is complete.

The horizontal distance between $p$ and $q$ (i.e., $|p_1-q_1|$) is smaller than the horizontal distance between $r$ and $s$. Recall that $v_t$ is either $r-s$ or $s-r$. Thus, the horizontal distance between $r$ and $s$ is equal to the first coordinate of the vector $v_t$, which is $x_t$.

Let ${\mathrm{\ell }}^{\prime }$ be the largest index for which ${\beta }_{p,{\mathrm{\ell }}^{\prime }}\ne {\beta }_{q,{\mathrm{\ell }}^{\prime }}$. Note that $\mathrm{\ell }\le {\mathrm{\ell }}^{\prime }$. If $\mathrm{\ell }={\mathrm{\ell }}^{\prime }$, then

and

Now assume that . We may assume, without loss of generality, that ${\beta }_{p,{\mathrm{\ell }}^{\prime }}=1$ and ${\beta }_{q,{\mathrm{\ell }}^{\prime }}=0$. Then (recall that $x_i=2^i$),

We conclude that , which is equivalent to . $◀$

Our approach will be to use multiple scaled and shifted copies of the construction in Theorem 8 to define a set $S$ of $n$ points in ${ℝ}^2$ for which $|A(S,m)|=\mathrm{\Omega }(n\log (m^2/n))$.

For $i=1,2,\mathrm{\dots },m+1$, we take $a_i=i$ and consider the corresponding vertical hyperplane $H_i$. For each $i=1,2,\mathrm{\dots },m$, the point set $S$ will contain exactly $n/m$ points in the vertical slab $⟦H_i,H_{i+1}⟧$.

Throughout the proof, we will use the following notation. Let $v_0,v_1,\mathrm{\dots },v_{k-1}$ be a sequence of pairwise distinct vectors in the plane. The hypercube-set defined by these vectors is the point set

For each $g=1,2,\mathrm{\dots },n/m$, we define a hypercube-set $Q_g$:

• $\mathrm{■}$

  Let $k_g=\lfloor \log (m/(2g-1))\rfloor$.

• $\mathrm{■}$

  For each $i=0,1,\mathrm{\dots },k_g-1$, let $x_{g,i}=(2g-1)\cdot 2^i$ and let $v_{g,i}=(x_{g,i},y_{g,i})$ be a vector, whose second coordinate $y_{g,i}$ will be defined later.

• $\mathrm{■}$

  Let $Q_g=Q(v_{g,0},v_{g,1},\mathrm{\dots },v_{g,k_g-1})$.

Since, for integers $g$, $g^{\prime }$, $i$, and $i^{\prime }$, $(2g-1)\cdot 2^i=(2g^{\prime }-1)\cdot 2^{i^{\prime }}$ if and only if $g=g^{\prime }$ and $i=i^{\prime }$, then all values $x_{g,i}$ are pairwise distinct.

To define the values $y_{g,i}$, we sort all vectors $v_{g,i}$ by their first coordinates. We go through the sorted sequence in decreasing order:

• $\mathrm{■}$

  For the vector with the largest first coordinate, we set its $y$-value to zero.

• $\mathrm{■}$

  For each subsequent vector $v_{g,i}$, we set $y_{g,i}$ to be an integer such that

  $$\Vert v_{g,i}\Vert >2\sum _{g^{\prime },i^{\prime }}\Vert v_{g^{\prime },i^{\prime }}\Vert ,$$

  (3)

  where the summation is over all pairs $g^{\prime },i^{\prime }$ for which $y_{g^{\prime },i^{\prime }}$ has already been defined (i.e., ).

We choose pairwise distinct real numbers , for $g=1,2,\mathrm{\dots },n/m$, and set

where $\mathrm{diam}(Q_g)$ denotes the diameter of the point set $Q_g$.

For each $g=1,2,\mathrm{\dots },n/m$ and $i=1,2,\mathrm{\dots },2g-1$, let

that is, $S_{g,i}$ is the translate of $Q_g$ by the vector $(i+{\epsilon }_g,2({(g-1)}^2+i-1)\mathrm{\Delta })$. We define $S^{\prime }$ to be the union of all these sets $S_{g,i}$, i.e.,

Note that the sets $S_{g,i}$ are pairwise disjoint: Indeed if $g\ne g^{\prime }$ or $i\ne i^{\prime }$, then the $y$-projections of $S_{g,i}$ and $S_{g^{\prime },i^{\prime }}$ (i.e., the sets of second coordinates) are disjoint by construction. Consequently, the size of the union of these point sets satisfies

For each $1\le g\le n/m$, by construction of $Q_g$ and the fact that the sets $S_{g,i}$ are disjoint translations of $Q_g$, each slab $⟦H_j,H_{j+1}⟧$ contains at most one point of ${\bigcup }_{i=1}^{2g-1}{S}_{g,i}$. Therefore, each slab $⟦H_j,H_{j+1}⟧$ contains at most $n/m$ points of $S^{\prime }$.

To obtain the final point set $S$ of size $n$, we add $n-|S^{\prime }|$ points to $S^{\prime }$ such that each slab $⟦H_j,H_{j+1}⟧$ contains exactly $n/m$ points of $S$, and the added points are sufficiently far from each other and from all points of $S^{\prime }$.

In the rest of this proof, we will prove the following claim: For each $g=1,2,\mathrm{\dots },n/m$, consider two binary strings of length $k_g$ that differ in exactly one position (recall that the number of such pairs of strings is equal to $k_g\cdot 2^{k_g-1}$). These strings correspond to two points of the hypercube-set $Q_g$. Thus, for any $i=1,2,\mathrm{\dots },2g-1$, they correspond to two points, say $r$ and $s$, in the set $S_{g,i}$. We claim that $r$ and $s$ form the closest pair in the set $⟦H_{\lfloor r_1\rfloor },H_{\lceil s_1\rceil }⟧\cap S$, where $r_1$ and $s_1$ are the first coordinates of $r$ and $s$, respectively (assuming that ). Note that we take the floor and the ceiling, because $r_1$ and $s_1$ are not integers. This claim will imply that

Since $k_g>\log \left(\frac{m}{2g-1}\right)-1$, we get

Since each term in the first summation is larger than the last term, which is larger than $(m/4)\log (m^2/(2n))$, we get

Since $m>3\sqrt{n}$,

We conclude that

It remains to prove the above claim. Let $g$ and $i$ be integers with $1\le g\le n/m$ and $1\le i\le 2g-1$. Consider two binary strings of length $k_g$ that differ in exactly one position; denote this position by $t$. Let $r$ and $s$ be the two corresponding points of $S_{g,i}$. Note that the vector $v_{g,t}$ is equal to either $r-s$ or $s-r$.

We may assume, without loss of generality, that . To prove that $r$ and $s$ form the closest pair in the set $⟦H_{\lfloor r_1\rfloor },H_{\lceil s_1\rceil }⟧\cap S$, we consider an arbitrary pair $p$ and $q$ of points in $⟦H_{\lfloor r_1\rfloor },H_{\lceil s_1\rceil }⟧\cap S$ such that $\{p,q\}\ne \{r,s\}$. We will show that .

Let $g^{\prime }$, $g^{\prime \prime }$, $i^{\prime }$, and $i^{\prime \prime }$ be such that $p\in S_{g^{\prime },i^{\prime }}$ and $q\in S_{g^{\prime \prime },i^{\prime \prime }}$. If $g^{\prime }\ne g^{\prime \prime }$ or $i^{\prime }\ne i^{\prime \prime }$, then