Tangent Spheres and Integer Distances

Authors: David Eppstein

The Erdős-Anning theorem states that any point set for which all distances are integers, in a Euclidean space of any dimension, must be either finite or collinear. We prove the same result in hyperbolic space of any dimension. A quantitative form of our result also extends for the first time to Euclidean spaces of dimension greater than two: if a set of points with integer distances in $\mathbb{E}^D$ or $\mathbb{H}^D$ has a subset of $D+1$ points in general position whose diameter is $d$, then the whole set has size $O(D(d+1)^D)$. To prove these results we formulate a lemma that, if the graph of external tangencies of a system of spheres in Euclidean or hyperbolic space contains a $K_{a,b}$ subgraph for $a,b\ge 3$, then the sets of spheres on each side of this biclique have centers that lie on a hyperplane. This lemma also implies that, in multilateration (determining a position from differences of distances to known landmarks), $D+1$ non-coplanar landmarks always suffice to limit the position to two possibilities.