Unit Distances in Three Dimensions

Haim Kaplan, Jirí Matousek, Zuzana Safernová, Micha SharirComb. Probab. Comput 2011 · DOI · OpenReview

TL;DR

This paper tackles the classic "unit distances problem" in 3D, asking for the maximum number of pairs of points that are exactly one unit apart. The authors improve a decades-old upper bound from $O(n^{3/2} \alpha(n))$ to $O(n^{3/2})$, a subtle but significant refinement achieved using a powerful new technique called polynomial partitioning.

What Problem Does This Paper Address?

The "unit distances problem" asks: given $n$ points in a space, what's the maximum number of pairs of points that are exactly a distance of 1 apart? While this problem is well-studied in 2D, it's also interesting in higher dimensions. For $d \ge 4$ dimensions, the answer is known to be $O(n^2)$. However, for $d=2$ and $d=3$, the problem is much harder. The paper focuses on the 3D case. The best known upper bound before this work was $O(n^{3/2} \alpha(n))$ by Clarkson et al. in 1990, where $\alpha(n)$ is the very slowly growing inverse Ackermann function. This left a gap between the lower bound of $\Omega(n^{4/3} \log \log n)$ and the upper bound. This paper aims to close that gap slightly by removing the $\alpha(n)$ factor.

Methods

The core of the paper's method is the polynomial partitioning technique, recently developed by Guth and Katz. This technique is a powerful tool for analyzing geometric incidence problems. Here's a simplified breakdown:

  1. Polynomial Partitioning: The idea is to use a carefully chosen polynomial to "cut" the space. This polynomial's zero set divides the space into regions (cells). The key is that this polynomial can be constructed to bisect any given set of points, meaning it doesn't leave too many points in any single region. The paper uses a multi-level version of this technique.
  2. Incidence Counting: The problem of counting unit distances is reframed as counting incidences between points and spheres. Specifically, if we have $n$ points $P = \{p_1, \dots, p_n\}$, the number of unit distances is half the number of incidences between these points and the set of unit spheres $\Sigma = \{\sigma_1, \dots, \sigma_n\}$, where $\sigma_i$ is the unit sphere centered at $p_i$.
  3. Recursive Decomposition: The polynomial partitioning is applied recursively. First, the set of points $P$ is partitioned. Then, a subset of points lying on the zero set of the first polynomial is further partitioned using a second polynomial. This second polynomial is constructed to be co-prime with the first one, which is a crucial technical challenge. This recursive process helps reduce the problem to lower-dimensional settings or simpler structures.
  4. Algebraic Geometry Tools: The analysis relies heavily on tools from real algebraic geometry, such as Harnack's theorem (bounding the number of connected components of algebraic curves) and Bézout's theorem (bounding intersection points of algebraic curves).

What's new is the application of this multi-level polynomial partitioning to the 3D unit distances problem, specifically the technical challenge of ensuring co-primality of the partitioning polynomials in successive steps.

Datasets

Not discussed in the paper. The paper deals with abstract sets of $n$ points in $\mathbb{R}^3$.

Key Insights and Ideas

  • The Power of Polynomial Partitioning: The paper demonstrates the versatility of the Guth-Katz polynomial partitioning technique beyond its original planar applications. It shows how this method can be adapted to higher dimensions and more complex geometric structures.
  • Co-primality is Key for Recursion: The main technical hurdle in extending the polynomial partitioning to multiple levels is ensuring that the polynomials used in subsequent steps are co-prime with those from previous steps. This is essential to avoid degenerate cases where the dimension reduction fails.
  • Reframing the Problem: The insight that the unit distances problem can be elegantly framed as an incidence problem between points and spheres is fundamental. This allows the application of powerful combinatorial and algebraic geometry tools.
  • Subtle Improvement: While the improvement from $O(n^{3/2} \alpha(n))$ to $O(n^{3/2})$ might seem small, it's significant because it removes a factor that depends on the specific structure of the point set and provides a cleaner, more fundamental bound.

Key Results

The paper's main result is the improved upper bound for the number of unit distances determined by $n$ points in $\mathbb{R}^3$:

  • Theorem 1: The number of unit distances in any set of $n$ points in $\mathbb{R}^3$ is $O(n^{3/2})$.

This slightly improves the bound of Clarkson et al. [5] from $O(n^{3/2} \alpha(n))$ to $O(n^{3/2})$.

Limitations and Future Work

  • Multi-level Polynomial Partitions: The authors acknowledge that the general problem of constructing co-prime polynomial partitions for many recursive steps remains an open issue. Their current approach handles two levels effectively, but extending it to more levels for higher dimensions or more complex incidence problems would require a more systematic approach.
  • Higher Dimensions and Surfaces: The paper focuses on unit spheres. Zahl [25] has extended similar results to incidences between points and more general surfaces in 3D. The authors suggest that their analysis could be similarly extended, but it would involve more complicated arguments.
  • Generalizing the Co-prime Construction: The paper mentions that an appropriate extension of Lemma 4 (which deals with constructing co-prime polynomials) to quotient rings defined by two or more polynomials is still an open issue. This is a key area for future research if the technique is to be applied more broadly.

Summary updated

Abstract

We show that the number of unit distances determined by n points in ℝ3 is O(n3/2), slightly improving the bound of Clarkson, Edelsbrunner, Guibas, Sharir and Welzl [5], established in 1990. The new proof uses the recently introduced polynomial partitioning technique of Guth and Katz [12]. While this paper was still in a draft stage, a similar proof of our main result was posted to the arXiv by Joshua Zahl [28].
BibTeX
@inproceedings{kaplan2011unit,
  author = {Haim Kaplan and Jirí Matousek and Zuzana Safernová and Micha Sharir},
  title = {{Unit Distances in Three Dimensions}},
  booktitle = {Comb. Probab. Comput},
  year = {2011},
  doi = {10.3929/ethz-b-000049783},
}

Loading related content...

Figure