# Non-Euclidean Erdős–Anning Theorems

David Eppstein Department of Computer Science, University of California,
Irvine. Donald Bren Hall, Irvine, CA 92697, USA<EMAIL_ADDRESS>
###### Abstract

The Erdős–Anning theorem states that every point set in the Euclidean plane
with integer distances must be either collinear or finite. More strongly, for
any (non-degenerate) triangle of diameter $\delta$, at most $O(\delta^{2})$
points can have integer distances from all three triangle vertices. We prove
the same results for any strictly convex distance function on the plane, and
analogous results for every two-dimensional complete Riemannian manifold of
bounded genus and for geodesic distance on the boundary of every three-
dimensional Euclidean convex set. As a consequence, we resolve a 1983 question
of Richard Guy on the equilateral dimension of Riemannian manifolds. Our
proofs are based on the properties of additively weighted Voronoi diagrams of
these distances.

##  1 Introduction

A well-known theorem of Paul Erdős and Norman Anning states that every point
set in the Euclidean plane with integer distances must be either collinear or
finite [1, 11]. More strongly, for any (non-degenerate) triangle of diameter
$\delta$, at most $O(\delta^{2})$ points can have integer distances from all
three triangle vertices. When the whole point set has diameter $D$, its number
of points is $O(D)$ [29]. In contrast, as Euler already observed, there exist
infinite non-collinear point sets of bounded diameter with all distances
rational, for instance, dense subsets of a unit circle [12, 14].

There are many metrics other than Euclidean distance for which we might ask
similar questions. One obstacle to generalizing the Erdős–Anning theorem to
other metrics is that its usual proof is heavily based on algebraic geometry.
In the Euclidean plane, the locus of points whose distances to two given
points differ by a fixed integer is a branch of a hyperbola. Therefore, the
points with integer distances to three non-collinear points lie at the
intersection points of two finite families of hyperbolas. Hyperbolas are
algebraic curves of degree two, and by Bezout’s theorem two hyperbolas have at
most four crossings, so these two finite families have finitely many
intersection points. But it is not obvious how to extend this argument to
metrics for which the the corresponding curves are more complicated or non-
algebraic. Erdős and Anning originally used a different argument using
trigonometric inequalities [1], but its generalization is also non-obvious.

A second obstacle is, of course, that analogous statements are untrue for some
metrics. For the $L_{1}$ or $L_{\infty}$ distances in the plane, for instance,
the integer lattice provides a familiar example of an infinite set that is not
collinear and has only integer distances. Thus, generalizations of the theorem
to other families of metrics must avoid families that include $L_{1}$ or
$L_{\infty}$.

In this paper we prove the following generalized versions of the Erdős–Anning
theorem:

> For any strictly convex distance function on $\mathbb{R}^{2}$, every point
> set with integer distances must be either collinear or finite. For any (non-
> degenerate) triangle of diameter $\delta$, at most $O(\delta^{2})$ points
> can have integer distances from all three triangle vertices. If a set with
> integer distances has diameter $D$, it has at most $O(D)$ points. (Section
> 2)
>
> For any two-dimensional complete Riemannian manifold of bounded genus $g$,
> every point set with integer distances must be either be finite or have
> shortest curves through each triple of points that all lie on a single
> geodesic. If some three of the points do not lie on a single shortest curve,
> and have diameter $\delta$, at most $O((g+1)\delta^{2})$ points can have
> integer distances from these three points. (Section 3)
>
> For geodesic distance on the boundary of a convex set in $\mathbb{R}^{3}$,
> every point set with integer distances must either be finite or have
> shortest curves through each triple of points that all lie on a single
> geodesic. If some three of the points do not lie on a single shortest curve,
> and have diameter $\delta$, at most $O(\delta^{2})$ points can have integer
> distances from these three points. If a set with integer distances has
> diameter $D$, it has at most $O(D^{4/3})$ points. (Section 4)

Our proofs replace the intersection properties of low-degree algebraic curves
with the geometric and topological properties of additively weighted Voronoi
diagrams. Our results for Riemannian manifolds resolve a question posed in
1983 by Richard Guy [13], on the _equilateral dimension_ of Riemannian
manifolds, the maximum number of points at unit distance from each other in
these manifolds. For complete Riemannian 2-manifolds of bounded genus, we
bound the equilateral dimension by a function of the genus (Corollary 20) but
for locally Euclidean incomplete Riemannian 2-manifolds, for complete
Riemannian 2-manifolds of unbounded genus, and for complete Riemannian metrics
on $\mathbb{R}^{3}$, the equilateral dimension is unbounded (Example 6 and
Example 7).

##  2 Convex distance functions

A _convex distance function_ on $\mathbb{R}^{d}$ can be defined from any
centrally symmetric compact convex body $K$. The resulting function
$d_{K}(p,q)$ is the smallest scale factor $s$ such that a copy of $K$, scaled
by $s$ and centered at $p$, contains $q$. Any convex distance function defines
a norm on $\mathbb{R}^{d}$, $||p||_{K}=d_{K}(0,p)$. In the reverse direction,
the closed unit ball $\\{p\mid||p||\leq 1\\}$ of any norm $||\cdot||$ can be
used to define a convex distance function. A convex set is _strictly convex_
if its boundary does not contain any line segment, and a _strictly convex
distance function_ is a convex distance function defined from a strictly
convex set. Convex distance functions obey all the requirements of a metric
space, including the triangle inequality. For strictly convex distance
functions and non-collinear triples of points $p$, $q$, $r$, they obey a
strict form of the triangle inequality [7]:

$d_{K}(p,r)<d_{K}(p,q)+d_{K}(q,r).$

Examples of strictly convex distance functions include the Minkowski $L_{p}$
distances for $1<p<\infty$, obtained from the convex body

$K_{p}=\left\\{(x_{1},x_{2},\dots x_{d})\biggm{|}\sum_{i=1}^{d}x_{i}^{p}\leq
1\right\\}.$

For $p=1$ and for the limiting case $p=\infty$ one obtains distance functions
that are convex but not strictly convex. For $p=2$ we recover the familiar
Euclidean distance.

A _curve_ , in one of these spaces, is just a continuous function from the
unit interval $[0,1]$ to the space. Its _endpoints_ are the values of this
function at $0$ and $1$. If $C$ is a curve for a space with distance $d$, we
may define its length as

$\lim_{n\to\infty}\sum_{i=1}^{n}d\left(C\left(\frac{i-1}{n}\right),C\left(\frac{i}{n}\right)\right),$

when this limit exists. Convex distance functions define _geodesic metric
spaces_ , spaces in which the distance between any two points equals the
length of a shortest curve between the points. For strictly convex distance
functions, this shortest curve is unique: it is just the _line segment_
between its two points. It is convenient to combine these observations about
shortest curves with the triangle inequality to obtain the following
observation about distances:

######  Observation 1 (Lipschitz property of distances).

Let $p$, $q$, and $r$ be points of a geodesic space with distance $d$, and let
$C$ be a curve with endpoints $q$ and $r$, of length $\ell$. Then

$-\ell\leq d(p,q)-d(p,r)\leq\ell,$

with equality on the left side only when $C$ traces without backtracking a
subset of a shortest curve from $p$ to $r$, and with equality on the right
side only when $C$ traces without backtracking a subset of a shortest curve
from $q$ to $p$.

Thus, when the space is given by a strictly convex distance function, and when
the difference of distances equals the length of the curve $C$, the three
points $p$, $q$, and $r$ must be collinear, and curve $C$ must form a segment
of their line.

###  2.1 Examples

In this section we provide examples of integer distance sets for different
convex distance functions.

Figure 1: Integer $L_{1}$ (left) and $L_{\infty}$ distances in the integer
grid (Example 1). The yellow shaded regions are the unit balls for these two
distances.

######  Example 1.

The integer grid $\\{(x,y)\mid x,y\in\mathbb{Z}\\}$ has integer distances for
the $L_{1}$ distance (the sum of absolute differences of coordinates) and
$L_{\infty}$ distance (maximum absolute difference of coordinates); see Fig.
1. Both the $L_{1}$ and $L_{\infty}$ distance are convex distance functions,
but are not strictly convex distance functions. The unit ball of the $L_{1}$
distance is a $45^{\circ}$-rotated square with vertices $(0,\pm 1)$ and $(\pm
1,0)$, while the unit ball of $L_{\infty}$ distance is an axis-parallel square
with vertices $(\pm 1,\pm 1)$.

######  Example 2.

Let $S$ be any finite set of points in the plane for which all $\tbinom{n}{2}$
lines determined by $S$ have distinct slopes. Then there exists a strictly
convex distance function $d_{K}$ that assigns integer distances to each pair
of points in $S$. To construct $d_{K}$, consider the system of unit vectors
obtained by normalizing the vector differences of each pair of points; these
form a centrally symmetric set on the unit circle, and by assumption they are
distinct. Let $\varepsilon$ be a sufficiently small number that expanding any
subset of these unit vectors by a factor of $1+\varepsilon$ would preserve the
strict convex position of all the vectors. Scale the unit circle and the
vectors on it so that, when using the result as the unit ball for a convex
distance function, all distances in $S$ become larger than $1/\varepsilon$.
Round each of these distances down to an integer, and expand each of the
corresponding vectors by the same factor (at most $1+\varepsilon$) by which
its distance was decreased. Construct $K$ as any strictly convex set through
the resulting vectors, for instance by connecting them in cyclic order using
circular arcs of sufficiently large radius. Then for this choice of $K$, each
distance in $S$ becomes its rounded value, which by construction is an
integer.

A similar construction shows that any countable set of points for which all
lines have distinct slopes can be made to have rational (but not integer)
distances for a strictly convex distance function, obtained by adding the
points one at a time and perturbing the distance function for each added point
without changing the previous distances.

Figure 2: Construction for an infinite non-geodesic set with integer distances
for a convex but not strictly convex distance function $d_{K}$ (Example 3).

######  Example 3.

For any convex distance functions $d_{K}$ that is not strict, there exist
infinite sets that have integer distances but that do not belong to a single
shortest curve. To construct such a set, note that if $d_{K}$ is convex but
not strictly convex, then the boundary of $K$ contains a line segment. Place
two or more points along this segment, at equal rational distances $\delta$
according to $d_{K}$, and add two more points at the origin and at its
reflection across this line segment, each having unit distance to the entire
line segment according to $d_{K}$. Scale this system of points by the
denominator of $\delta$ to produce a finite set of points with integer
distances, having a parallelogram as its convex hull. Connecting multiple
translated copies of this parallelogram by identifying their copies of the
origin and its reflection (Fig. 2) produces the desired infinite non-geodesic
set with integer distances.

######  Example 4.

Euclidean distance is a convex distance function, and there exist infinite
dense sets of points on the unit circle with rational Euclidean distances [12,
14]. One construction for such a system of points uses complex number
coordinates for the points of the plane, and consists of the complex numbers
$\\{q^{2j}\mid j\in\mathbb{Z}\\}$ where $q=\tfrac{a}{c}+i\tfrac{b}{c}$ is a
rational point on the unit circle derived from an integer right triangle with
side lengths $a$, $b$, and $c$. Geometrically, this point set is obtained from
a single point by repeatedly rotating by twice the angle of the
triangle.111This construction is essentially due to Harborth [14] but he
states it incorrectly as using all integer multiples of the angle rather than
only the even multiples. Fig. 3 shows an example derived from the 3-4-5 right
triangle. Arbitrarily large finite non-collinear point sets at integer
distances can be obtained by taking a finite subset of this infinite set
(possibly including also the center of the circle) and scaling it to clear the
denominators in its coordinates.

Figure 3: The points on the unit sphere whose angles are even multiples of the
angles of a 3-4-5 right triangle have pairwise rational distances.

It is an open problem whether there exist arbitrarily-large sets of points at
integer Euclidean distances that have no three points in a line and no four
points on a circle [10]. The largest such sets known have only seven points
[18, 19].

###  2.2 Voronoi diagrams and star-shaped cells

A _Voronoi diagram_ of a finite set of points (called _sites_) in a metric
space $(X,d)$ subdivides the space into subsets according to which of the
sites is closest. More precisely, each site $s_{i}$ has a (closed) cell
$V_{i}$ associated with it, where

$V_{i}=\left\\{p\in X\biggm{|}d(p,s_{i})\leq\min_{j\neq i}d(p,s_{j})\right\\}$

is the set of points in the metric space for which the distance to site
$s_{i}$ is less than or equal to the distance to any other site $s_{j}$. We
will only use Voronoi diagrams of finite sets (in fact, of at most three
sites), so we only define and discuss the properties of these diagrams for
finite sets of sites.

The intersection of any collection of Voronoi cells is the locus of points
having equal distances to their sites. When $X$ has the topology of the plane,
the _bisector_ of a pair of sites (the intersection of their Voronoi cells) is
often (but not always) a curve, and a non-empty intersection of three or more
sites is often (but not always) an isolated point or points, called _Voronoi
vertices_. We will use _additively weighted_ Voronoi diagrams, in which each
site $s_{i}$ has a weight $w_{i}$ associated with it, and in which the
distances in the definition of cells are modified by adding these weights:

$V_{i}=\left\\{p\in X\biggm{|}d(p,s_{i})+w_{i}\leq\min_{j\neq
i}d(p,s_{j})+w_{j}\right\\}.$

Voronoi diagrams have been the object of intensive study, including Voronoi
diagrams for convex distance functions [7, 16, 20], for points on a sphere
[24, 3, 26], for points in the hyperbolic plane [9, 28, 4], orbifolds [23],
and for more general Riemannian manifolds [21]. Additively weighted Voronoi
diagrams are also a standard concept [6, 17], and confusingly, are sometimes
called _hyperbolic Dirichlet tessellations_ despite their use of Euclidean
distance [2], because the boundaries of their cells are arcs of hyperbolas
(the same hyperbolas used in the Erdős–Anning proof). We did not find works
combining both additive weights and non-Euclidean distances.

Figure 4: Three star-shaped sets, each shown with a point in its kernel.

The _kernel_ of a subset $S$ of the plane is defined as the set of points $p$
such that, for every point $q$ in $S$, the line segment $pq$ belongs to $S$.
$S$ is convex if and only if its kernel coincides with $S$. Weakening this
formulation of convexity, $S$ is defined to be _star-shaped_ if its kernel is
non-empty. (See Fig. 4. Note that, according to this definition, star-shaped
sets are not required to form topological disks, and the empty set is not
star-shaped.) It is known that, for instance, the Voronoi cells of unweighted
convex distance functions are star-shaped topological disks [7]. For
additively weighted Voronoi diagrams, we should be a little more careful,
because of the possibility that a Voronoi cell can degenerate to a line
segment, a single point, or the empty set, but in the Euclidean case they are
again known to be star-shaped when non-empty [2].

######  Lemma 2.

For additively weighted Voronoi diagrams of 2-dimensional strictly convex
distance functions, every non-empty Voronoi cell is star-shaped with its site
in its kernel.

###### Proof.

The star-shaped property is an immediate consequence of the Lipschitz property
of distances. If site $s_{i}$ has the minimum weighted distance to a given
point $p$, then for any other point $q$ on line segment $ps_{i}$, the weighted
distance from $s_{i}$ to $q$ is less by $d(p,q)$, while other weighted
distances decrease by at most the same amount, so the weighted distance from
$s_{i}$ remains minimum. Thus, if $p$ belongs to the Voronoi cell of $s_{i}$,
so does every point $q$ on line segment $ps_{i}$. ∎

###  2.3 Degenerate and non-degenerate sites

In unweighted Voronoi diagrams, every cell is a topological disk (or the whole
space), having its site in its interior. That is not true for additively
weighted Voronoi diagrams, but the cells that do not have their site in their
interior have a very special structure, which we examine next.

######  Definition 1.

Define a _degenerate site_ of an additively weighted Voronoi diagram of a
2-dimensional strictly convex distance function to be a site that belongs to
the Voronoi cell of another site. Define a _non-degenerate site_ to be a site
that is not degenerate.

Figure 5: An additively weighted Voronoi diagram with two degenerate sites
(red and green) and two non-degenerate sites (yellow and blue). The red site
has equal weighted distance to itself and to the yellow site; its Voronoi cell
(shown as a red line segment) extends along a ray, away from the yellow site,
to the boundary of the yellow Voronoi cell. The green site has larger weighted
distance to itself than to the blue site, so its Voronoi cell is empty. The
Voronoi cells for the yellow and blue sites together cover the plane,
separated from each other by the central vertical line. The distance function
is unspecified; it could be Euclidean, or any other strictly convex distance
function whose unit disk has vertical reflection symmetry (so that the
bisector of the two horizontally-aligned yellow and blue points is a vertical
line).

For examples of degenerate and non-degenerate sites, see Fig. 5. The next
lemma explains the shapes of the cells in this example:

######  Lemma 3.

Let $s_{i}$ be a degenerate site of an additively weighted Voronoi diagram of
a 2-dimensional strictly convex distance function, with $s_{i}$ belonging to
the Voronoi cell $V_{j}$ of another site $s_{i}$. Let $R$ be a ray on line
$s_{i}s_{j}$ with $s_{i}$ as its initial point, extending away from $s_{j}$.
Then either $s_{i}$ is empty, or $V_{i}=R\cap V_{j}$.

###### Proof.

If the weighted distance from $s_{i}$ to $s_{j}$ is less than the weighted
distance from $s_{i}$ to itself, then $s_{i}$ does not belong to its own
Voronoi cell, and the only possibility according to Lemma 2 is that $V_{i}$ is
empty. Otherwise, at $s_{i}$, the weighted distances to $s_{i}$ and $s_{j}$
are equal. Let $R$ be as described in the statement of the lemma. By the
Lipschitz property of distances, every point of $R$ has equal weighted
distance to $s_{i}$ and to $s_{j}$, and every other point in the plane has
smaller weighted distance to $s_{j}$ than to $s_{i}$. Therefore, the set of
points whose weighted distance to $s_{i}$ is minimum (among weighted distances
to all sites) is exactly $R\cap V_{j}$. ∎

By repeatedly using Lemma 3 to replace the Voronoi cells of degenerate sites
with supersets that are also Voronoi cells, until no more such replacements
can be performed, we obtain:

######  Corollary 4.

In an additively weighted Voronoi diagram of a 2-dimensional strictly convex
distance function, every point belongs to the Voronoi cell of at least one
non-degenerate site.

Note that Corollary 4 would not be true if we allowed infinite sets of sites.
Instead of defining degeneracy of a site by its membership in other cells, we
have an equivalent characterization by its position within its own cell:

######  Lemma 5.

A site $s_{i}$ of an additively weighted Voronoi diagram of a 2-dimensional
strictly convex distance function is non-degenerate if and only if it is an
interior point of its cell $V_{i}$.

###### Proof.

If $s_{i}$ is an interior point of $V_{i}$, $V_{i}$ cannot be a subset of a
ray (which has no interior points), and it follows from Lemma 3 that $s_{i}$
is non-degenerate. If $s_{i}$ is not an interior point of $V_{i}$, then every
neighborhood of $s_{i}$ has points that are not in $V_{i}$, and therefore
there exists some other cell $V_{j}$ intersecting this neighborhood. Because
there are only finitely many sites, we can reverse the quantifiers: there
exists some other cell $V_{j}$ that intersects every neighborhood of $s_{i}$.
But because cells are closed sets, this implies that $s_{i}\in V_{j}$ and
$s_{i}$ is degenerate. ∎

As the next lemma shows, each ray with a non-degenerate site as its initial
point passes through at most one boundary point of its Voronoi cell.

######  Lemma 6.

Let $s_{i}$ be a non-degenerate site of an additively weighted Voronoi diagram
of a 2-dimensional strictly convex distance function, let $L$ be a line
segment in $V_{i}$ having $s_{i}$ as an endpoint, and let $p$ be a point in
the relative interior of $L$. Then $p$ is interior to $V_{i}$.

Figure 6: Figure for the proof of Lemma 6: a site $s_{i}$, a segment $L$
within Voronoi cell $V_{i}$, and a point $p$ in the relative interior of $L$
that is not interior to $V_{i}$. The lemma proves that this situation cannot
exist by considering cases for the location of $s_{j}$, another site with the
same distance to $p$ as $s_{i}$.

###### Proof.

Suppose for a contradiction that $p$ is not interior to $V_{i}$. Then by
finiteness of the number of sites, there must exist another site $s_{j}$ such
that every neighborhood of $p$ contains points of $V_{j}\setminus V_{i}$.
Because Voronoi cells are closed, $p$ belongs to $V_{j}$ as well as to
$V_{i}$, and has equal weighted distance to $s_{i}$ and $s_{j}$. We now
distinguish three cases for the possible location of $s_{j}$:

  * •

Suppose that $s_{j}$ does not lie on the line containing $L$, as shown in Fig.
6, or lies on the opposite side from $p$ as $s_{i}$ on this line or great
circle. Then by the Lipschitz property of distances, all points of $L$ that
are on the opposite side from $p$ as $S_{i}$ would have smaller weighted
distance to $s_{j}$ than to $s_{i}$, because the distance from $s_{i}$
increases at the same rate as distance from $p$ along $L$, while the distance
from $s_{j}$ cannot increase as quickly. But this contradicts the assumption
that some of these points belong to $V_{i}$.

  * •

Suppose that $s_{j}$ lies on segment or arc $ps_{i}$. Then $s_{j}\in V_{i}$,
and by Lemma 3 its Voronoi cell $V_{j}$ is a subset of $V_{i}$, contradicting
the assumption that $N$ contains a point of $V_{j}\setminus V_{i}$.

  * •

The only remaining case is that $s_{i}$ lies on line segment $ps_{j}$. But
this lies within $V_{j}$ by Lemma 2, so $s_{i}\in V_{j}$, contradicting the
assumption that $s_{i}$ is non-degenerate.

As all cases lead to a contradiction, the assumption that $p$ is not interior
to $V_{i}$ must be false. ∎

###  2.4 Intersections of non-degenerate cells

In the previous subsection, we studied the shapes of individual cells of
additively weighted Voronoi diagrams. In this section we instead consider the
intersection patterns of cells.

Figure 7: Figure for the proof of Lemma 7: if a point $p$ could belong to the
interior of the Voronoi cell $V_{i}$ for non-degenerate site $s_{i}$, and also
belong to the Voronoi cell for $s_{j}$, then some point $q$ past $p$ on the
same ray would also belong to $V_{i}$, contradicting the Lipschitz property of
distances.

######  Lemma 7.

Let $s_{i}$ and $s_{j}$ be non-degenerate sites of an additively weighted
Voronoi diagram for a 2-dimensional strictly convex distance function. Then
the interior of $V_{i}$ is disjoint from $V_{j}$, and vice versa.

###### Proof.

Suppose for a contradiction that there existed a point $p$ interior to $V_{i}$
that also belonged to $V_{j}$. Then segments $ps_{i}$ and $ps_{j}$ must be
disjoint except for their shared endpoint, for otherwise one would be a subset
of the other, and one of the two sites would belong to the Voronoi cell of the
other, contradicting the assumption that both are non-degenerate. Because $p$
belongs to both $V_{i}$ and $V_{j}$, it has equal weighted distance to both
sites. Because $p$ is interior to $V_{i}$, we can extend line segment $ps_{i}$
within a neighborhood of $p$ inside $V_{i}$, to obtain a line segment $qs_{i}$
that still remains entirely interior to $V_{i}$ (Fig. 7). By the Lipschitz
property of distances, $q$ is farther than $p$ from $s_{i}$ by an amount equal
to the distance from $p$ to $q$, while the distance from $q$ to $s_{j}$ cannot
increase as quickly. Therefore, $q$ belongs to the Voronoi diagram of $V_{j}$
but not of $V_{i}$, contradicting our construction of $q$ as a point in
$V_{i}$. This contradiction shows that our assumption of a point interior to
$V_{i}$ that also belonged to $V_{j}$ cannot hold: no such point exists.
Symmetrically, no point interior to $V_{j}$ can also belong to $V_{i}$. ∎

######  Lemma 8.

Let $s_{i}$ and $s_{j}$ be distinct non-degenerate sites of an additively
weighted Voronoi diagram of a 2-dimensional strictly convex distance function,
and let $p$ and $q$ be distinct points of $V_{i}$ and $V_{j}$ respectively.
Then line segments (or arcs) $ps_{i}$ and $qs_{j}$ are disjoint.

###### Proof.

Otherwise, one of these two segments would contain a point in the relative
interior of the other segment or arc. By Lemma 6 this point would be interior
to its Voronoi cell, contradicting Lemma 7. ∎

Finally, we consider intersections of three Voronoi cells, in the main lemma
needed for our proof of our non-Euclidean Erdős–Anning theorem:

######  Lemma 9.

Let $s_{i}$, $s_{j}$, and $s_{k}$ be non-collinear sites of an additively
weighted Voronoi diagram of a 2-dimensional strictly convex distance function.
Then $V_{i}\cap V_{j}\cap V_{k}$ consists of at most two points.

###### Proof.

Without loss of generality we may consider that these are the only three sites
of the Voronoi diagram, because adding more sites can only reduce the points
in $V_{i}\cap V_{j}\cap V_{k}$ by causing some of those points to belong to
Voronoi cells of other sites. By Lemma 6 and Lemma 7, the whole space is
covered by the cells of non-degenerate sites, with disjoint interiors. We
distinguish cases by how many of the three given sites are non-degenerate:

  * •

Suppose that there is only one non-degenerate site, without loss of generality
$s_{i}$. Then, $V_{i}$ is the whole space, and $V_{j}$ and $V_{k}$ lie on rays
extending away from $s_{i}$. These rays diverge from each other (by non-
collinearity) and must be disjoint, so $|V_{i}\cap V_{j}\cap V_{k}|=0$.

  * •

In the next case, there are two non-degenerate sites, without loss of
generality $s_{i}$ and $s_{j}$. Because it is degenerate, $s_{k}$ belongs to
at least one of their Voronoi cells, without loss of generality $V_{i}$. By
Lemma 3, $V_{k}$ has the form $R\cap V_{i}$, where $R$ is a ray collinear with
$s_{i}$. By Lemma 6, only the farthest point from $s_{i}$ on $R\cap V_{i}$ can
be a boundary point of $V_{i}$; all the other points are interior to $V_{i}$.
By Lemma 7, only the one boundary point can also belong to $V_{j}$. Thus, in
this case, $|V_{i}\cap V_{j}\cap V_{k}|\leq 1$ again.

Figure 8: Figure for the proof of Lemma 9: Three non-degenerate sites $s_{i}$,
$s_{j}$, and $s_{k}$, and three points belonging to the intersection of
Voronoi cells $V_{i}\cap V_{j}\cap V_{k}$, would form a drawing of the non-
planar graph $K_{3,3}$.

  * •

In the remaining case, all three sites are non-degenerate. In particular, none
of them belong to $V_{i}\cap V_{j}\cap V_{k}$. Consider the system of line
segments connecting each site to each point of $V_{i}\cap V_{j}\cap V_{k}$. By
Lemma 8 these line segments cannot intersect except at shared endpoints, so
they form a planar drawing of a complete bipartite graph with the three sites
on one side of its bipartition and the points of $V_{i}\cap V_{j}\cap V_{k}$
on the other side. If there could be three points in $V_{i}\cap V_{j}\cap
V_{k}$, this would give a planar drawing of $K_{3,3}$, a non-planar graph
(Fig. 8). Therefore, $|V_{i}\cap V_{j}\cap V_{k}|\leq 2$.∎

###  2.5 Erdős–Anning theorems for strict convex distance functions

######  Theorem 1.

Let $s_{1}$, $s_{2}$, and $s_{3}$ be three non-collinear points of a
2-dimensional strictly convex distance function $d$. Then the number of points
that can have integer distances to all three of $s_{1}$, $s_{2}$, and $s_{3}$
is $O\bigl{(}d(s_{1},s_{2})\cdot d(s_{1},s_{3})\bigr{)}$.

###### Proof.

Let $p$ be a point with integer distances to all three of $s_{1}$, $s_{2}$,
and $s_{3}$. Consider the additively weighted Voronoi diagram of these three
sites, with weights $w_{i}=d(s_{1},p)-d(s_{i},p)$. Then at $p$, the three
additively weighted distances all equal $d(s_{1},p)$, so all three sites are
equal nearest neighbors. This means that $p$ must belong to the triple
intersection of Voronoi cells $V_{1}\cap V_{2}\cap V_{3}$.

Weight $w_{1}$ is identically zero, and by the triangle inequality the
remaining two weights have absolute values $|d(d_{1},p)-d(s_{2},p)|$ and
$|d(s_{1},p)-d(s_{3},p)|$ that are at most $d(s_{1},s_{2})$ and
$d(s_{1},s_{3})$ respectively. Therefore, there are at most
$\bigl{(}2d(s_{1},s_{2})+1\bigr{)}\cdot\bigl{(}2(d(s_{1},s_{3})+1\bigr{)}$
combinations of weights defining an additively weighted Voronoi diagram for
which $p$ might be a triple intersection point, and at most two triple
intersection points per diagram, giving a total of at most
$2\bigl{(}2d(s_{1},s_{2})+1\bigr{)}\cdot\bigl{(}2(d(s_{1},s_{3})+1\bigr{)}$
possible points that can have integer distances to all three of $s_{1}$,
$s_{2}$, and $s_{3}$. ∎

As an immediate corollary, we have the following generalization of the
Erdős–Anning theorem:

######  Theorem 2.

If a set $S$ of points of a 2-dimensional strictly convex distance function
has the property that all distances between points of $S$ are integers, then
$S$ is finite or collinear.

###### Proof.

If $S$ is not collinear, it has three non-collinear points to which we can
apply Theorem 1. ∎

###  2.6 Diameter bounds

The number of points in a set with integer distances can also be bounded
linearly in the diameter of the set, generalizing a result of Solymosi [29]
for Euclidean distance.

######  Theorem 3.

If a set $S$ of points of a 2-dimensional strictly convex distance function
has diameter $D$ (measured according to that distance function), and all
distances in $S$ are integers, then $|S|=O(D)$, with a constant of
proportionality that depends on the distance function.

###### Proof.

Let $\rho$ be the minimum Euclidean distance to the origin of the unit ball of
the given distance function $d$. Then scaling both $S$ and the distance
function by $1/\rho$ produces a distance function whose unit ball contains a
given circle, without changing the distance between any two of the scaled
points in $S$. Let $\xi$ be the maximum Euclidean distance from the origin of
this scaled unit ball; note that, if we treat the distance function as fixed,
then $\xi$ is a constant. After this scaling, the function measured by $d$ is
upper bounded by the Euclidean distance, and lower bounded by Euclidean
distance divided by $\xi$. Therefore, the Euclidean diameter of $S$ (as
scaled) is also at most $D$.

Figure 9: Figure for the proof of Theorem 3: After enclosing the given points
in a bounding box $B$ of side length three times the diameter $D$, $s_{1}$ is
the point whose Euclidean Voronoi cell $V_{1}$ has the smallest intersection
with $B$, $s_{2}$ is its nearest neighbor, $m$ is their midpoint, and right
triangle $ps_{1}m$ is chosen to have as large an area as possible within
$V_{1}\cap B$. In the case shown, $p$ is on the boundary of $B$, at distance
greater than $D$ from $s_{1}$, from which it follows that
$d(s_{1},s_{2})=O(D/n)$.

Enclose $S$ in a square bounding box of (Euclidean) side length $D$, and
center this within a larger square $B$ of side length $3D$, so that all points
of $S$ are at Euclidean distance at least $D$ from the boundary of $B$.
Construct the (Euclidean) Voronoi diagram of $S$, let $s_{1}$ be the point of
$S$ whose Voronoi cell $V_{1}$, intersected with $B$, has the smallest
Euclidean area, $\leq 9D^{2}/n=O(D^{2}/n)$. Let $s_{2}$ be the Euclidean
nearest neighbor of $s_{1}$ in $S$, let $m$ be the midpoint of $s_{1}$ and
$s_{2}$, and construct a right triangle $ps_{1}m$ with right angle at $s_{1}$,
contained in $V_{1}\cap B$, with the largest possible Euclidean area. (See
Fig. 9 for an example.) We distinguish two cases:

  * •

If $p$ is on the boundary of $B$, as shown in Fig. 9, it is at Euclidean
distance $\geq D$ from $s_{1}$. In order for right triangle $ps_{1}s_{2}$ to
have area $O(D^{2}/n)$, at most the area of the set $V_{1}\cap B$ that
contains it, edge $s_{1}s_{2}$ must have Euclidean length $O(D/n)$, and
therefore also $d(s_{1},s_{2})=O(D/n)$. For this distance to be a nonzero
integer, $n$ must be $O(D)$.

  * •

Otherwise, $p$ is on the boundary of $V_{1}$, and equidistant (in Euclidean
distance) from $s_{1}$ and some site $s_{3}$ which cannot be collinear with
$s_{1}s_{2}$. Because the Euclidean distances and distances according to $d$
are proportional, $d(s_{1},s_{2})\cdot d(s_{1},s_{3})=O(D^{2}/n)$. It follows
from Theorem 1 that $n=O(D^{2}/n)$ and therefore that $n=O(D)$.∎

The examples of $n\times n$ integer grids for the $L_{1}$ or $L_{\infty}$
distance show that the assumption of strict convexity is necessary for this
result.

##  3 Riemannian manifolds

In this section we prove a form of the Erdős–Anning theorem for two-
dimensional complete Riemannian manifolds. These can be defined intrinsically
(without respect to an embedding) as smooth manifolds equipped with a smoothly
varying inner product structure on their tangent space. “Completeness” in this
context means that all Cauchy sequences converge; for instance, puncturing the
Euclidean plane by removing the origin would produce a space that is not
complete. By the Nash embedding theorem [27] it is equivalent (and may be
easier) to think of these as two-dimensional surfaces, smoothly embedded into
a Euclidean space of bounded dimension, with distance measured by the
Euclidean length of curves on the surface. Standard examples of such spaces
include the Euclidean plane itself, the surface of any smooth convex body in
three dimensions such as a sphere, and the hyperbolic plane.

One complication in these spaces is that their usual analogues of straight
lines, _geodesics_ , are only locally shortest curves between their points:
two or points may belong to a common geodesic that does not contain the
shortest curve between them. Indeed, in some cases a geodesic may cross itself
or form a dense subset of its surface. For this reason, we will generally work
with shortest curves (between some two points of the space) rather than
geodesics. These curves may not be unique: for instance, for antipodal points
on a sphere, there are infinitely many shortest curves, covering the whole
sphere. By the Hopf–Rinow theorem [15], every complete Riemannian manifold has
a shortest curve between every two points. Thus, these are geodesic metric
spaces, and in particular the Lipschitz property of distances (1) applies to
them.

We will not assume that the surfaces we consider are orientable. One way to
parameterize a two-dimensional surface, without assuming orientability, is by
its _Euler genus_ , the number $2-\chi$ where $\chi$ is the Euler
characteristic. It is possible for a Riemannian manifold to have infinite
genus, but (except for Example 7, which motivates this limitation) we will
only work with surfaces of bounded genus.

###  3.1 Examples

We have the following analogue of Example 2:

######  Example 5.

Consider any finite set of three or more points $S$ on a unit sphere, no three
of which belong to a great circle. Then each two points of $S$ have a unique
shortest curve which does not pass through other points of $S$. Perturb the
sphere by placing a small smooth bump along each shortest curve, increasing
the distance between its two points to a rational number without changing the
other distances, and then scale the result to clear the denominators of these
rational distances. The result is a complete Riemannian manifold of Euler
genus zero with an arbitrary finite number of points at integer distances from
each other.

It is necessary to assume that our Riemannian manifolds are complete, because
of the following example:

######  Example 6.

Consider the points coordinatized by two real numbers $r$ and $\theta$, with
$r$ positive and $\theta$ arbitrary, and with the standard locally Euclidean
geometry of the polar coordinate system. This can be thought of as a cone with
an infinite angle at its removed apex [30]. Its Euler genus is zero
(topologically it is just an open halfplane). When two of its points have
$\theta$-coordinates that differ by at least $\pi$, their distance equals the
sum of their $r$-coordinates (distances from the removed apex). Therefore, the
points $\\{(\tfrac{1}{2},i\pi)\mid i\in\mathbb{Z}\\}$ form an infinite set at
unit distance from each other. They have no shortest curves, because any such
curve would pass through the missing apex point.

Figure 10: Five small spheres connected in pairs by cylindrical tubes.
Smoothing the sphere-cube edges produces a complete Riemannian manifold.
Public domain image from
https://commons.wikimedia.org/wiki/File:Schlegel_wireframe_5-cell.png.

As the next example shows, to obtain a generalization of the Erdos–Anning
theorem to complete Riemannian manifolds, we will also need to assume bounded
genus, and our bounds on numbers of points in integer distance sets will need
to depend on the genus.

######  Example 7.

For any $n$, one may form a complete Riemannian manifold from $n$ spheres,
connected by cutting out disks from pairs of spheres, attaching a cylindrical
tube between the boundaries of the two disks, and smoothing the parts of the
surface where the disks meet the tubes. This construction may be performed
abstractly as a topological space; it is not necessary to embed the spheres
and tubes into three-dimensional space, allowing the lengths of the tubes to
be adjusted. Let $S$ consist of one point per sphere, for spheres small enough
that all distances within one sphere are less than $1/3$; then by adjusting
the lengths of all the tubes, all distances between points of $S$ can be made
equal to one. This construction produces arbitrarily large finite sets of
points at unit distance from each other, with genus $O(n^{2})$. Because they
all have the same distance, no three of these points belong to a shortest
curve.

The connected sum of an infinite sequence of examples of this type for
$n=4,5,6,\dots$, obtained by using tubes to connect the example for each $n$
to the examples for $n-1$ and $n+1$, forms a single complete Riemannian
manifold of infinite genus in which one can find arbitrarily large (but
nevertheless finite) sets of points that are all at unit distance from each
other.

Although the topological structure of this example is complicated, it can be
embedded in a distance-preserving way into a Riemannian metric on
$\mathbb{R}^{3}$. For each $n$, choose the spheres and tubes of the $n$-point
example to have a small enough radius that they can all be smoothly embedded
within a unit ball of $\mathbb{R}^{3}$, coiling the tubes to cause them to
have the desired lengths. Form the connected sum of these examples as before
and embed it smoothly in $\mathbb{R}^{3}$ using disjoint unit balls for each
term in the connected sum. Thicken the resulting smoothly embedded surface $S$
by a small amount (varying smoothly over the surface) chosen to be small
enough that the thickened set remains smoothly embedded in $\mathbb{R}^{3}$,
and give the resulting thickened set a Riemannian metric that agrees with the
metric on $S$ (and the Euclidean distance of $\mathbb{R}^{3}$) in directions
parallel to $S$, but that is longer in the direction perpendicular to $S$ by a
factor that varies smoothly from very large for points on $S$ to one at the
boundary of this thickened set. Then, for the remaining points of
$\mathbb{R}^{3}$, outside the thickened set, use the usual Euclidean distance.
By choosing this perpendicular lengthening factor large enough, it is possible
to ensure that escaping from $S$ to the boundary of the thickened set takes
more than unit distance, and that distances within $S$ are preserved.

Richard Guy asked whether the _equilateral dimension_ of Riemannian manifolds,
the maximum cardinality of a set of points in the manifold for which all
distances are one, can be bounded by a function of the dimension of the
manifold [13]. A positive answer was known only for the case of complete
Riemannian manifolds of bounded curvature [22]. Example 6 provides a
counterexample for locally Euclidean and topologically simple but incomplete
Riemannian 2-manifolds. Example 7 provides a counterexample for complete
Riemannian 2-manifolds of unbounded genus and for topologically simple
complete Riemannian 3-manifolds. On the other hand, our generalization of the
Erdős–Anning theorem to complete Riemannian 2-manifolds of bounded genus also
provides a bound on the equilateral dimension of these manifolds, as a
function of their genus (Corollary 20).

Our proof of the Erdős–Anning theorem for strictly convex distance functions
relied on the non-planarity of the graph $K_{3,3}$. For complete Riemannian
manifolds of bounded genus we will need to reach farther for graphs that
cannot be embedded, as the following example shows.

Figure 11: An embedding of $K_{3,6}$ with shortest-curve edges on a hexagonal
torus (Example 8). The colors indicate the Voronoi diagram of the points on
the three-vertex side of the bipartition.

######  Example 8.

Form a complete Riemannian manifold (the _hexagonal torus_) by gluing opposite
edges of a Euclidean regular hexagon. After this gluing step, the six vertices
of the hexagon become two points of the hexagonal torus. Let $S$ be the set
consisting of these two points together with the center of the hexagon. Then
the hexagonal torus has six points equidistant from the three points of $S$.
Connecting the three points of $S$ by shortest curves to each of these six
points forms an embedding of the graph $K_{3,6}$ on the hexagonal torus (Fig.
11).

###  3.2 Voronoi cells

Our definitions of Voronoi diagrams for finite sets of sites, additively
weighted Voronoi diagrams, and Voronoi cells apply to any metric space. We may
define kernels and star-shaped sets, in complete Riemannian manifolds, by
analogy to their Euclidean definitions. We define the _kernel_ of a set $S$ to
be the set of points $p$ such that, for every point $q\in S$, every shortest
curve between $p$ and $q$ belongs to $S$. We define $S$ to be _star-shaped_ if
its kernel is non-empty. Then we have the following analogue of Lemma 2. The
proof, which depends only on the space being geodesic and on the Lipschitz
property of distances, is unchanged.

######  Lemma 10.

For additively weighted Voronoi diagrams of complete Riemannian manifolds,
every non-empty Voronoi cell is star-shaped with its site in its kernel.

As before, we define a _degenerate site_ to be a site that belongs to the
Voronoi cell of another site, and a _non-degenerate site_ to be a site that is
not degenerate. To formulate an analogue of Lemma 3, we also need a definition
of a ray in a complete Riemannian manifold. To do this, we use the
_exponential map_. Given a point $p$ of the manifold, and a vector $v$ in the
tangent space at $p$, the exponential map takes $v$ to $\exp_{p}v$, another
point in the manifold obtained by following a geodesic from $p$ for a length
and direction specified by $v$. For Riemannian manifolds in general, this is
defined only for a neighborhood of the origin in the tangent space, but for
complete Riemannian manifolds it is defined for the whole tangent space. For
any point $p$ of the manifold, there is a number $r>0$, the _injectivity
radius_ , such that the exponential map is an injection on vectors in the
tangent space at $p$ with radius $<r$, and not an injection for vectors with
radius $\leq r$. The exponential map is a smooth topological equivalence (a
diffeomorphism) between the disk of vectors of radius $<r$ and its image, a
neighborhood of $p$ in the manifold. We define a _ray_ in a complete
Riemannian manifold to be a set of the form

$\left\\{\exp_{p}cv\mid 0<c\right\\}$

for a fixed choice of $p$ (the starting point or _apex_ of the ray) and $v$ (a
vector specifying the direction of the ray), and for all positive scalars $c$.

Another complication here is that, for convex distance functions, the
intersection of a ray with a star-shaped set (having its apex in the kernel)
is a line segment, and therefore a shortest curve. For complete Riemannian
manifolds, a ray may continue through a star-shaped set past the last point
for which it forms a shortest curve, or may even have a disconnected
intersection with the set. It may also pass through some points of the
manifold more than once. In a Voronoi diagram, we define the _Voronoi segment_
of a ray, having one of its sites $s_{i}$ as an apex, to be the union of all
shortest curves from points in $V_{i}$ to $s_{i}$ that lie along the same ray.

######  Lemma 11.

Let $s_{i}$ be a degenerate site of an additively weighted Voronoi diagram of
a complete Riemannian manifold, with $s_{i}$ belonging to the Voronoi cell
$V_{j}$ of another site $s_{j}$. Let $R_{j}$ be a ray with apex $s_{j}$
containing a shortest curve from $s_{i}$ to $s_{j}$, and let $R_{i}$ be a ray
with apex $s_{i}$ continuing in the same direction, away from $s_{i}$. Then
either $s_{i}$ is empty, or $V_{i}$ is the intersection of $R_{i}$ with the
Voronoi segment of $R_{j}$.

###### Proof.

As in the proof of Lemma 3, if the weighted additive distance from $s_{i}$ to
$s_{j}$ is less than the weighted distance from $s_{i}$ to itself, then
$s_{i}$ does not belong to its own Voronoi cell and by Lemma 10 the cell must
be empty. Otherwise, at $s_{i}$, the weighted distances to $s_{i}$ and $s_{j}$
are equal. Because the lengths of curves along rays increase at the same rate
as distance traveled along a ray, the weighted lengths of curves along $R_{i}$
and $R_{j}$ remain equal for all points of $R_{i}$. At every point of the
Voronoi segment, this weighted distance is the minimum distance to a site, and
at every point of the past the endpoint of the Voronoi segment, it is not. ∎

By repeatedly using Lemma 11 to replace the Voronoi cells of degenerate sites
with supersets that are also Voronoi cells, until no more such replacements
can be performed, we obtain an analogue of Corollary 4:

######  Corollary 12.

In an additively weighted Voronoi diagram of a complete Riemannian manifold,
every point belongs to the Voronoi cell of at least one non-degenerate site.

We also have the following analogue of Lemma 5:

######  Lemma 13.

A site $s_{i}$ of an additively weighted Voronoi diagram of a 2-dimensional
complete Riemannian manifold is non-degenerate if and only if it is an
interior point of its cell $V_{i}$.

The proof is the same as that for Lemma 5.

We interpreted Lemma 6 as stating that each ray with a non-degenerate site as
its initial point passes through at most one boundary point of its Voronoi
cell. This is not true for complete Riemannian manifolds, because rays can re-
enter the Voronoi cell after the end of the Voronoi segment of the ray. On the
other hand, a Voronoi segment of bounded length may have its endpoint in the
interior of a cell, and not pass through any boundary points of the cell.
Nevertheless, we have the following analogue of Lemma 6:

######  Lemma 14.

Let $s_{i}$ be a non-degenerate site of an additively weighted Voronoi diagram
of a 2-dimensional complete Riemannian manifold, let $L$ be a Voronoi segment
in $V_{i}$ having $s_{i}$ as an endpoint, and let $p$ be a point in the
relative interior of $L$. Then $p$ is interior to $V_{i}$.

###### Proof.

As in the proof of Lemma 6, the only other possibility is that there is some
other Voronoi cell $V_{j}$ also containing $p$, such that every neighborhood
of $p$ contains points of $V_{j}\setminus V_{j}$. Then the shortest curves
from $p$ to $s_{i}$ and to $s_{j}$ cannot follow the same ray from $p$, else
$s_{i}$ would be degenerate (contradicting the assumption in the statement of
the lemma) or $s_{j}$ would be degenerate (contradicting the assumption that
$V_{j}\setminus V_{i}$ is nonempty). For any point $q$ past $p$ on $L$, there
would exist curves of equal length from $q$ to $s_{i}$ along $L$, and from $q$
to $s_{j}$ along $L$ to $p$ and then from $p$ to $s_{j}$; but because the
curve to $s_{j}$ turns at $p$ it cannot be a shortest curve as it can be
shortcut near $p$, so $q$ is closer to $s_{j}$ than $s_{i}$. But this would
contradict the definition of $L$ as a Voronoi segment. ∎

###  3.3 Intersections of non-degenerate cells

Continuing the analogy from convex distance functions to Riemannian manifolds,
we have the following analogue of Lemma 7. The proof is somewhat different
because of the possibility that a point interior to a Voronoi cell may
nevertheless be an endpoint of a Voronoi segment.

######  Lemma 15.

Let $s_{i}$ and $s_{j}$ be non-degenerate sites of an additively weighted
Voronoi diagram for a 2-dimensional complete Riemannian manifold. Then the
interior of $V_{i}$ is disjoint from $V_{j}$, and vice versa.

###### Proof.

Suppose for a contradiction that there existed a point $p$ interior to $V_{i}$
that also belonged to $V_{j}$. Then any shortest curves $ps_{i}$ and $ps_{j}$
must be disjoint except for their shared endpoint, for otherwise one would be
a subset of the other, and one of the two sites would belong to the Voronoi
cell of the other, contradicting the assumption that both are non-degenerate.
Because $p$ is interior to $V_{i}$, there must be some point $q\neq p$ on
segment $ps_{j}$ that also belongs to $V_{i}$. But by the Lipschitz property
of distances, the weighted distance to to $s_{j}$ decreases more quickly along
curve $pq$ than the weighted distance to $s_{i}$, a contradiction. ∎

Continuing the analogy, we have:

######  Lemma 16.

Let $s_{i}$ and $s_{j}$ be distinct non-degenerate sites of an additively
weighted Voronoi diagram of a 2-dimensional complete Riemannian manifold, and
let $p$ and $q$ be distinct points of $V_{i}$ and $V_{j}$ respectively. Then
line segments (or arcs) $ps_{i}$ and $qs_{j}$ are disjoint.

###### Proof.

Otherwise, one of these two segments would contain a point in the relative
interior of the other segment or arc. By Lemma 14 this point would be interior
to its Voronoi cell, contradicting Lemma 15. ∎

To formulate an analogue of Lemma 9 we must first account for examples like
Example 8 in which triples of Voronoi cells have more than two points of
intersection, corresponding to drawings of graphs $K_{3,a}$ with $a>2$ and
with all edges drawn as shortest curves.

######  Lemma 17.

On a surface of Euler genus $g$, the maximum number $a$ such that $K_{3,a}$
can be drawn without crossings on the surface is at most $2g+2$.

###### Proof.

In any drawing of $K_{3,a}$ on any surface, all faces of the drawing have at
least four sides, and each edge forms exactly two sides of faces (not
necessarily distinct). Therefore, if $V$, $E$, and $F$ are the sets of
vertices, edges, and faces of the drawing, we have

$2|E|\geq 4|F|.$

We also have

$|V|-|E|+|F|\geq 2-g$

by the definition of the Euler characteristic, where the inequality comes from
the fact that we are not assuming that the faces of the drawing are disks.
Using the first inequality to eliminate $|F|$ from the second gives

$|V|-\frac{1}{2}|E|\geq 2-g.$

or equivalently

$|E|\leq 2|V|+2g-4.$

The graph $K_{3,a}$ has $|V|=3+a$ and $|E|=3a$. In order to have $3a\leq
2(3+a)+2g-4$, we must have $a\leq 2g+2$. ∎

This is a known result; see, e.g., Bouchet [5], who credits the complete
characterization of the genus of complete bipartite graphs to several works of
Ringel from the mid-1960s. The Euler genus zero case of this lemma is the fact
that $K_{3,3}$ is non-planar, while the Euler genus two case includes the fact
that $K_{3,7}$ cannot be drawn on a torus. In these cases, the lemma is tight:
$K_{3,2}$ is planar and Example 8 shows that $K_{3,6}$ is toroidal.

Finally, this allows us to bound the number of triple intersections of Voronoi
cells:

######  Lemma 18.

Let $s_{i}$, $s_{j}$, and $s_{k}$ be three sites of an additively weighted
Voronoi diagram of a 2-dimensional complete Riemannian manifold of Euler genus
$g$, with none of the three sites belonging to any shortest curve between the
other two sites. Then $V_{i}\cap V_{j}\cap V_{k}$ consists of at most $2g+2$
points.

###### Proof.

Without loss of generality we may consider that these are the only three sites
of the Voronoi diagram, because adding more sites can only reduce the points
in $V_{i}\cap V_{j}\cap V_{k}$ by causing some of those points to belong to
Voronoi cells of other sites. By Lemma 14 and Lemma 15, the whole space is
covered by the cells of non-degenerate sites, with disjoint interiors. We
distinguish cases by how many of the three given sites are non-degenerate:

  * •

Suppose that there is only one non-degenerate site, without loss of generality
$s_{i}$. Then, $V_{i}$ is the whole space, and $V_{j}$ and $V_{k}$ lie on
Voronoi segments of $s_{i}$. These segments are distinct (else one of $s_{j}$
and $s_{k}$ would lie on a shortest curve from $s_{i}$ to the other). A point
$p$ interior to one Voronoi segment cannot belong to another Voronoi segment,
because if it did the points past $p$ on the first segment would have an
equally short curve to $s_{i}$ that follows the first segment to $p$ and then
the second curve to $s_{i}$, but such a non-geodesic curve cannot be a
shortest curve (it could be made shorter by adding a small shortcut near $p$).
Therefore, in this case the only point of intersection can be a shared
endpoint of the Voronoi segments of $s_{i}$ that contain $s_{j}$ and $s_{k}$,
giving $|V_{i}\cap V_{j}\cap V_{k}|\leq 1$.

  * •

In the next case, there are two non-degenerate sites, without loss of
generality $s_{i}$ and $s_{j}$. Because it is degenerate, $s_{k}$ belongs to
at least one of their Voronoi cells, without loss of generality $V_{i}$. By
Lemma 3, $V_{k}$ is the intersection of a ray from $s_{k}$ with a Voronoi
segment of $V_{i}$. By Lemma 14 and Lemma 15, only the endpoint of this
Voronoi segment can belong to $V_{j}$. Thus, in this case, $|V_{i}\cap
V_{j}\cap V_{k}|\leq 1$ again.

  * •

In the remaining case, all three sites are non-degenerate. In particular, none
of them belong to $V_{i}\cap V_{j}\cap V_{k}$. Consider the system of Voronoi
segments connecting each site to each point of $V_{i}\cap V_{j}\cap V_{k}$.
These line segments cannot intersect except at shared endpoints, so they form
a planar drawing of a complete bipartite graph with the three sites on one
side of its bipartition and the points of $V_{i}\cap V_{j}\cap V_{k}$ on the
other side. By Lemma 17, $|V_{i}\cap V_{j}\cap V_{k}|\leq 2g+2$.∎

###  3.4 Erdős–Anning theorems for Riemannian manifolds

######  Theorem 4.

Let $s_{1}$, $s_{2}$, and $s_{3}$ be three points of a 2-dimensional complete
Riemannian manifold of Euler genus $g$, with distance function $d$. Suppose
also that there is no shortest curve containing all three of these points.
Then the number of points that can have integer distances to all three of
$s_{1}$, $s_{2}$, and $s_{3}$ is $O\bigl{(}(g+1)\cdot d(s_{1},s_{2})\cdot
d(s_{1},s_{3})\bigr{)}$.

Except for the factor of $g$ coming from Lemma 18, the proof is the same as
for Theorem 1. For this theorem, the possibility that all triples of points
lie on shortest curves (preventing the theorem from being applied) corresponds
to the possibility of all points being collinear in the Euclidean plane or for
convex distance functions. It is a strengthening of the more obvious
generalization of collinearity, that all points of $S$ lie on a common
geodesic:

######  Lemma 19.

Let $S$ be a set of three or more points of a complete Riemannian manifold
such that each three points of $S$ belong to a shortest curve. Then $S$ is a
subset of a geodesic, and every shortest curve between pairs of points in $S$
lies along this geodesic.

###### Proof.

Let $s_{1}$ be any of the points, and consider the system of rays containing
shortest curves to all the other points. Suppose for a contradiction that
there are two rays $R_{2}$ and $R_{3}$ in this system of rays, containing
shortest curves from $s_{1}$ to points $s_{2}$ and $s_{3}$ in $S$, and that
these two rays are distinct and non-opposite. Then if $s_{1}$ were on a
shortest path from $s_{2}$ to $s_{3}$, then there would be a shortest curve
from $s_{2}$ to $s_{3}$ that follows $R_{2}$ from $s_{2}$ to $s_{1}$ and then
follows $R_{2}$ from $s_{1}$ to $s_{3}$. This cannot happen, because a
shortest curve that turns from one ray to another at $s_{1}$ could be shortcut
by a different curve in a neighborhood of $s_{1}$. Alternatively, if $s_{2}$
were on a shortest curve from $s_{1}$ to $s_{3}$, then we could get a shortest
curve from $s_{1}$ to $s_{3}$ that follows $R_{2}$ from $s_{1}$ to $s_{2}$,
turns at $s_{2}$, and then continues along the $R_{3}$ from $s_{2}$ to
$s_{3}$, again an impossibility. The case that $s_{3}$ is on a shortest curve
from $s_{1}$ to $s_{2}$ is symmetric. So none of the three points can be the
middle point of a shortest curve containing all three points. This
contradiction to the assumption of the lemma implies that rays $R_{2}$ and
$R_{3}$ cannot exist, and that the system of rays contains either a single ray
or two opposite rays. In either case, these two rays, and therefore all points
of $S$, lie on a single geodesic.

If some two points $s_{2}$ and $s_{3}$ had a shortest curve that did not lie
along this geodesic, then we could apply this same argument to the rays at
$s_{2}$ containing the shortest curve to $s_{1}$ (along the geodesic through
all points of $S$) and the ray containing the shortest curve from $s_{2}$ to
$s_{3}$ (not along this geodesic), obtaining the same contradiction. Therefore
all shortest curves lie on the same geodesic. ∎

The conclusion of this lemma cannot be strengthened to state that each pair of
points in $S$ has a unique shortest curve. For instance, consider an even
number of points equally spaced on the equator of a sphere. In this example,
each point has two shortest curves to its opposite point. A set of points
whose shortest curves all lie on a single geodesic might still not have the
property that each three points belong to a shortest curve: consider, for
instance, three equally spaced points on the equator of a sphere.

Combining Theorem 4 with Lemma 19 gives us the following generalization of the
Erdős–Anning theorem:

######  Theorem 5.

If a set $S$ of points of a 2-dimensional complete Riemannian manifold of
bounded genus has the property that all distances between points of $S$ are
integers, then either $S$ is finite or all triples of points in $S$ are
subsets of shortest curves along a single geodesic of the manifold.

We also have the following diameter bound, weaker than in the Euclidean or
convex distance function case:

######  Theorem 6.

If a set $S$ of points of a 2-dimensional complete Riemannian manifold of
bounded genus $g$ has integer distances and diameter $D$, then
$|S|=O(gD^{2})$.

###### Proof.

If $S$ has three points not all on a single shortest curve, this follows from
Theorem 4. Otherwise, the points all have shortest curves along a geodesic.
Let $C$ be a shortest curve of length $D$ between some two points of $S$. If
$C$ covers all points of $S$, there are at most $D+1$ points. Otherwise, let
$s_{1}$ and $s_{2}$ be the two endpoints of $C$, and let $s_{3}$ be any point
not covered by $C$. For $s_{1}$, $s_{2}$, and $s_{3}$ to be part of a shortest
curve, the curve must have $s_{1}$ and $s_{2}$ as endpoints, for otherwise we
would have a shortest curve that includes a segment from $s_{1}$ to $s_{2}$,
causing it to be longer than $D$. In this case, the only possibility is that
$s_{1}$ and $s_{2}$ have two shortest paths, and are at distance $D$ from each
other along a geodesic of length $2D$, so there are at most $2D$ points in
$S$. ∎

######  Corollary 20.

The equilateral dimension of a 2-dimensional complete Riemannian manifold of
bounded genus $g$ is $O(g)$.

##  4 Convex surfaces

In this section we extend our results on Riemann manifolds to non-smooth
surfaces of non-negative curvature. The restriction to non-negative curvature
is motivated by Example 6, which shows that even a single point of negative
curvature can be an obstacle to Erdős–Anning theorems. For concreteness, in
this section we define a _convex surface_ to mean either the boundary of a
convex subset of $\mathbb{R}^{3}$ with nonempty interior, or a degenerate
case, the double covering of a convex subset of $\mathbb{R}^{2}$ (obtained by
gluing two copies of the surface at their shared boundary). For instance, the
Euclidean plane is a convex surface in this sense: it is the boundary of a
halfspace. By results of Aleksei Pogorelov, a more abstract class of non-
smooth convex manifolds, topologically equivalent to a sphere and with total
Gaussian curvature $4\pi$, can be characterized as the bounded convex surfaces
in exactly this sense, including the degenerate case [8]. We measure the
distance on a convex surface as the infimum of lengths of curves on the
surface. By a compactness argument, each pair of points on the surface can be
connected by a curve of length equal to this distance, so this is a geodesic
metric space [25], and we can apply arguments involving the Lipschitz property
of distances. Every convex surface, in the sense described here, is
topologically a disk (like the Euclidean plane), a sphere (like a geometric
sphere, polyhedron, or double-covered topological disk), or an annulus (like
the boundary of an infinite cylinder); in particular, it has Euler genus zero.

Figure 12: A solid cone

The boundary of a (bounded) solid cone (Fig. 12) exhibits several of the
common geometric features of a convex surface. The base of the cone is a flat
disk; the sides of the cone have a flat surface metric (locally isometric to a
subset of the Euclidean plane) even though they are curved in three-
dimensional space. The circle where the base meets the sides is non-smooth;
each point has a neighborhood that approaches a Euclidean metric (equivalent
to that of a folded piece of paper) in the limit. The apex of the cone,
however, is not Euclidean, even in the limit: it has a positive angular
deficiency that can be measured by comparing the radius and circumference of
small metric disks around it. The total curvature of this surface is $4\pi$,
by the Gauss–Bonnet theorem, but in this case this curvature is concentrated
at the cone point (where it equals the angular deficit of this point) and
along the circle where the base and sides meet.

In general, when a shortest curve on a convex surface passes through a locally
Euclidean point, it must pass straight through it, in the local Euclidean
geometry of a neighborhood of a point. A curve that does not do this could be
shortcut to bypass the point. It is not possible for a shortest curve to pass
through a cone point (any point of positive angular deficiency): any curve
through such a point can be shortcut. Thus, we need only consider such points
as endpoints of shortest curves, not as their interior points.

######  Lemma 21.

Every point on a convex surface is either locally Euclidean or locally
equivalent to a cone point.

###### Proof.

For a point $p$ on a convex surface, let $C_{r}(p)$ denote the cone formed by
positive combinations of $p$ with the points at distance $r$ from $p$ on the
surface. Then $C_{r}$ is monotone in $r$: for $r^{\prime}<r$,
$C_{r}^{\prime}(p)\supset C_{r}(p)$, by convexity. By compactness of the space
of cones at a point $p$, in the limit as $r$ goes to zero, these cones
approach a limiting cone; call this limit $C_{0}(p)$. Let $B$ be the curve
obtained by intersecting the boundary of $C_{0}(p)$ with a unit sphere
centered at $p$. Then $B$ is convex, and lies in a half-sphere, again by
convexity of the convex surface. Thus, its length is at most $2\pi$. If it is
exactly $2\pi$, then $p$ is locally Euclidean; otherwise, it is locally
equivalent to a cone point with deficit equal to the difference between $2\pi$
and the length of $B$. ∎

###  4.1 Voronoi diagrams and their properties

For convex surfaces, we define star-shaped sets, additively weighted Voronoi
diagrams, rays, Voronoi segments, and degenerate and non-degenerate sites in
the same way as for Riemannian manifolds. One small difference is that a ray
can terminate, by hitting a cone point. Because every point is either locally
a cone point (with no geodesics through it) or locally Euclidean (with all
geodesics passing straight through it) the behavior of geodesics on convex
surfaces is much the same as for Riemannian manifolds: the cone points do not
affect them at at all, and the non-smooth geometry of the surface at the
remaining points does not affect our use of this geometry to prove properties
of these spaces. We have the following results, analogous to those for
Riemannian manifolds, with the same proofs:

######  Lemma 22.

For additively weighted Voronoi diagrams of convex surfaces, every non-empty
Voronoi cell is star-shaped with its site in its kernel.

###### Proof.

Same as for Lemma 2 and Lemma 10. ∎

######  Lemma 23.

Let $s_{i}$ be a degenerate site of an additively weighted Voronoi diagram of
a convex surface, with $s_{i}$ belonging to the Voronoi cell $V_{j}$ of
another site $s_{j}$. Let $R_{j}$ be a ray with apex $s_{j}$ containing a
shortest curve from $s_{i}$ to $s_{j}$, and let $R_{i}$ be a ray with apex
$s_{i}$ continuing in the same direction, away from $s_{i}$. Then either
$s_{i}$ is empty, or $V_{i}$ is the intersection of $R_{i}$ with the Voronoi
segment of $R_{j}$.

###### Proof.

Same as for Lemma 11. ∎

######  Corollary 24.

In an additively weighted Voronoi diagram on a convex surface, every point
belongs to the Voronoi cell of at least one non-degenerate site

######  Lemma 25.

A site $s_{i}$ of an additively weighted Voronoi diagram on a convex surface
is non-degenerate if and only if it is an interior point of its cell $V_{i}$.

###### Proof.

Same as for Lemma 5 and Lemma 13. ∎

######  Lemma 26.

Let $s_{i}$ be a non-degenerate site of an additively weighted Voronoi diagram
on a convex surface, let $L$ be a Voronoi segment in $V_{i}$ having $s_{i}$ as
an endpoint, and let $p$ be a point in the relative interior of $L$. Then $p$
is interior to $V_{i}$.

###### Proof.

Same as for Lemma 14, which depends only on the local Euclidean geometry of
the surface at an interior point of a shortest curve to argue that no curve
that bends at such a point can be shortest. Here we are using the fact that no
interior point of a shortest curve can be a cone point. ∎

######  Lemma 27.

Let $s_{i}$ and $s_{j}$ be non-degenerate sites of an additively weighted
Voronoi diagram on a convex surface. Then the interior of $V_{i}$ is disjoint
from $V_{j}$, and vice versa.

###### Proof.

Same as for Lemma 15. ∎

######  Lemma 28.

Let $s_{i}$ and $s_{j}$ be distinct non-degenerate sites of an additively
weighted Voronoi diagram on a convex surface, and let $p$ and $q$ be distinct
points of $V_{i}$ and $V_{j}$ respectively. Then line segments (or arcs)
$ps_{i}$ and $qs_{j}$ are disjoint.

###### Proof.

Same as for Lemma 16. ∎

######  Lemma 29.

Let $s_{i}$, $s_{j}$, and $s_{k}$ be three sites of an additively weighted
Voronoi diagram on a convex surface, with none of the three sites belonging to
any shortest curve between the other two sites. Then $V_{i}\cap V_{j}\cap
V_{k}$ consists of at most two points.

###### Proof.

Same as Lemma 18, noting that convex surfaces have Euler genus zero. ∎

###  4.2 Erdős–Anning theorems for convex surfaces

######  Theorem 7.

Let $s_{1}$, $s_{2}$, and $s_{3}$ be three points of a convex surface, with
distance function $d$. Suppose also that there is no shortest curve containing
all three of these points. Then the number of points that can have integer
distances to all three of $s_{1}$, $s_{2}$, and $s_{3}$ is
$O\bigl{(}d(s_{1},s_{2})\cdot d(s_{1},s_{3})\bigr{)}$.

###### Proof.

Same as for Theorem 1 and Theorem 4. ∎

######  Lemma 30.

Let $S$ be a set of three or more points of a convex surface such that each
three points of $S$ belong to a shortest curve. Then $S$ is a subset of a
geodesic, and every shortest curve between pairs of points in $S$ lies along
this geodesic.

###### Proof.

Same as for Lemma 19. ∎

######  Theorem 8.

If a set $S$ of points of a convex surface has the property that all distances
between points of $S$ are integers, then either $S$ is finite or all triples
of points in $S$ are subsets of shortest curves along a single geodesic.

###### Proof.

Same as for Theorem 5. ∎

Our diameter bound seems unlikely to be tight. It uses the following
preliminary lemmas.

Figure 13: Lemma 31: a short path connecting two of three points separated by
a convex set

######  Lemma 31.

Suppose that three given points in $\mathbb{R}^{d}$ are disjoint from an open
convex set $U$. Then two of the points can be connected by a curve disjoint
from $U$ of length at most twice their Euclidean distance.

###### Proof.

Consider the plane containing the three points; if $U$ does not intersect this
plane then the points can be connected directly. Within this plane draw a line
through each point, disjoint from $U$. If the three lines form a triangle or
unbounded three-sided region containing $U$, with the three points on its
sides, then one of its internal angles is at least $60^{\circ}$, and the curve
connecting two points through this angle has length at most twice the distance
between the points (Fig. 13; worst case: $U$ is an equilateral triangle and
the three points are its edge midpoints). If one of the three points is not on
a side of the region containing $U$, it can see the entire line through
another of the points, and be connected directly to that point. ∎

######  Lemma 32.

If $n$ points on a convex surface have diameter $D$ then some two of the
points have distance $O(D/\sqrt{n})$.

###### Proof.

Let the set of points be $S$. It lies within a ball of radius $D$ in
$\mathbb{R}^{3}$. Subdivide the ball by a grid of cubes, of side length
$O(D/\sqrt{n})$, positioned so that none of the given points lies on a cube
boundary, and discretize the convex set intersected with the ball by replacing
it with the set of cubes that it intersects. A cube $C$ that contains a point
of $S$ must be part of this discretized set of cubes, but it also must touch
(at least at a corner) a cube that is outside the set, because if all eight
cubes corner-adjacent to $C$ intersected or were within the surface, then the
convex hull of the intersection points in these cubes would entirely enclose
$C$, preventing it from including any part of the convex surface. Therefore,
$C$ is within $O(1)$ grid positions of a boundary square of the discretized
set of cubes. Any axis-parallel line can cross only two boundary squares (one
in each direction), so there are $O(n)$ such squares and $O(n)$ cubes that
contain points of $S$. By choosing the grid size appropriately, we can ensure
that fewer than $n/2$ cubes contain points of $S$, and therefore that some
cube, of side length $O(D/\sqrt{n})$, contains at least three points of $S$.
We consider two cases:

  * •

If the convex surface is non-degenerate (it bounds a convex set with non-empty
interior), then by Lemma 31, two of these three points are connected by a path
in space, disjoint from the interior of the given convex set, of length
$O(D/\sqrt{n})$, and hence are at geodesic distance $O(D/\sqrt{n})$ on the
convex surface.

  * •

Otherwise, the convex surface is a double-covered two-dimensional convex set,
two of the three points are on the same side of the double cover, and these
two points can be connected directly by a segment of length $O(D/\sqrt{n})$.

In either case, we have two points at geodesic distance $O(D/\sqrt{n})$. ∎

The example of an integer grid on a flat plane shows that the bound of Lemma
32 is tight.

######  Theorem 9.

If a set $S$ of points of a convex surface has integer distances and diameter
$D$, then $|S|=O(D^{4/3})$.

###### Proof.

Let $n$ be the size of $S$, and let its two closest such points be $p$ and
$q$, with distance $O(D/\sqrt{n})$ by Lemma 32. We distinguish two cases:

  * •

Suppose that all triples of points in $S$ that include both $p$ and $q$ belong
to shortest curves. Each such point must belong either to a ray from $p$
through $q$ or a ray from $q$ through $p$, with the ray containing a shortest
curve from $p$ to $q$. Further, this shortest curve (and hence these two rays)
must be unique, for if there were two shortest curves between $p$ and $q$, one
of them could be combined with part of a shortest curve from $p$ or $q$ to a
third point $r$ to form a shortest curve that passes through $q$ or $p$ at a
non-straight angle, an impossibility. Thus, there are two rays containing all
remaining points in $S$, and these points must lie at integer spacing along
these two rays, so there are $O(D)$ points in $S$ in total.

  * •

Otherwise, some point $r$ does not lie on a shortest curve with $p$ and $q$.
By Theorem 7, there can be $O(D^{2}/\sqrt{n})$ points in $S$. That is,
$n=O(D^{2}/\sqrt{n})$. Multiplying both sides by $\sqrt{n}$ and taking the
$2/3$ power gives the result.∎

##  5 Discussion

We have shown that integer-distance point sets are finite or collinear in
three broad classes of metric spaces each generalizing Euclidean distance in
the plane. The next natural direction to look for a further extension of these
results is in higher dimensions. Erdős and Anning state without proof that
their results extend to $d$-dimensional Euclidean space [1]. However, the
obvious attempt to generalize our proof to higher dimensions, by using
intersection patterns of $(d+1)$-tuples of Voronoi cells, does not work for
convex distance functions: there exist three-dimensional convex distance
functions for which some 4-tuple of points is equidistant from arbitrarily
many other points [16]. For Riemannian manifolds, the theorem does not
generalize, as Example 7 shows. Nevertheless, it would be interesting to study
similar questions for higher-dimensional uniform metrics, such as hyperbolic
space. It would also be of interest to strengthen the bound on diameter in
Theorem 6 and Theorem 9, if possible.

## References

  * [1] Norman H. Anning and Paul Erdős.  Integral distances.  Bulletin of the American Mathematical Society, 51(8):598–600, 1945.  doi:10.1090/S0002-9904-1945-08407-9.
  * [2] Peter F. Ash and Ethan D. Bolker.  Generalized Dirichlet tessellations.  Geometriae Dedicata, 20(2):209–243, 1986.  doi:10.1007/BF00164401.
  * [3] Jeffrey M. Augenbaum and Charles S. Peskin.  On the construction of the Voronoi mesh on a sphere.  Journal of Computational Physics, 59(2):177–192, 1985.  doi:10.1016/0021-9991(85)90140-8.
  * [4] Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud.  Hyperbolic Delaunay complexes and Voronoi diagrams made practical.  Journal of Computational Geometry, 5(1):56–85, 2014.  doi:10.20382/JOCG.V5I1A4.
  * [5] André Bouchet.  Orientable and non orientable genus of the complete bipartite graph.  Journal of Combinatorial Theory, Series B, 24:24–33, 1978.  doi:10.1016/0095-8956(78)90073-4.
  * [6] L. Paul Chew and Robert L. (Scot) Drysdale, III.  Generalization of Voronoi diagrams in the plane.  SIAM Journal on Computing, 10(1):73–87, 1981.  doi:10.1137/0210006.
  * [7] L. Paul Chew and Robert L. (Scot) Drysdale, III.  Voronoi diagrams based on convex distance functions.  In Joseph O’Rourke, editor, Proceedings of the First Annual Symposium on Computational Geometry, Baltimore, Maryland, USA, June 5–7, 1985, pages 235–244. Association for Computing Machinery, 1985.  doi:10.1145/323233.323264.
  * [8] Robert Connelly.  _Convex Polyhedra_ by A. D. Alexandrov.  SIAM Review, 48(1):157–160, March 2006.  URL: https://www.jstor.org/stable/204537, doi:10.1137/SIREAD000048000001000149000001.
  * [9] Olivier Devillers, Stefan Meiser, and Monique Teillaud.  The space of spheres, a geometric tool to unify duality results on Voronoi diagrams.  In Proceedings of the 4th Canadian Conference on Computational Geometry (CCCG ’92), pages 263–268, 1992.  URL: https://cccg.ca/proceedings/1992/Paper43.pdf.
  * [10] David Eppstein.  Forbidden Configurations in Discrete Geometry.  Cambridge University Press, 2018.  doi:10.1017/9781108539180.
  * [11] Paul Erdős.  Integral distances.  Bulletin of the American Mathematical Society, 51:996, 1945.  doi:10.1090/S0002-9904-1945-08490-0.
  * [12] Leonhard Euler.  Fragmenta arithmetica ex Adversariis mathematicis deprompta, C: Analysis Diophantea.  In Opera postuma, volume I, pages 204–263. Eggers, Petropolis, 1862.  Theorem 65, p. 229.  URL: https://scholarlycommons.pacific.edu/euler-works/806/.
  * [13] Richard K. Guy.  An olla-podrida of open problems, often oddly posed.  The American Mathematical Monthly, 90(3):196–200, 1983.  doi:10.2307/2975549.
  * [14] Heiko Harborth.  Integral distances in point sets.  In Charlemagne and his Heritage: 1200 Years of Civilization and Science in Europe, Vol. 2 (Aachen, 1995), pages 213–224. Brepols, Turnhout, Belgium, 1998.  doi:10.1484/M.STHS-EB.4.2017040.
  * [15] H. Hopf and W. Rinow.  Ueber den Begriff der vollständigen differentialgeometrischen Fläche.  Commentarii Mathematici Helvetici, 3(1):209–225, 1931.  doi:10.1007/BF01601813.
  * [16] Christian Icking, Rolf Klein, Ngọc-Minh Lê, and Lihong Ma.  Convex distance functions in 3-space are different.  Fundamenta Informaticae, 22(4):331–352, 1995.  doi:10.3233/FI-1995-2242.
  * [17] Menelaos I. Karavelas and Ioannis Z. Emiris.  Root comparison techniques applied to computing the additively weighted Voronoi diagram.  In Proceedings of the Fourteenth Annual ACM–SIAM Symposium on Discrete Algorithms, January 12–14, 2003, Baltimore, Maryland, USA, pages 320–329. ACM and SIAM, 2003.  URL: https://dl.acm.org/citation.cfm?id=644108.644161.
  * [18] Michael Kleber.  Encounter at far point.  Mathematical Intelligencer, 1:50–53, 2008.  doi:10.1007/BF02985756.
  * [19] Tobias Kreisel and Sascha Kurz.  There are integral heptagons, no three points on a line, no four on a circle.  Discrete & Computational Geometry, 39(4):786–790, 2008.  doi:10.1007/s00454-007-9038-6.
  * [20] Ngọc-Minh Lê.  On non-smooth convex distance functions.  Information Processing Letters, 63(6):323–329, 1997.  doi:10.1016/S0020-0190(97)00136-1.
  * [21] Greg Leibon and David Letscher.  Delaunay triangulations and Voronoi diagrams for Riemannian manifolds.  In Siu-Wing Cheng, Otfried Cheong, Pankaj K. Agarwal, and Steven Fortune, editors, Proceedings of the Sixteenth Annual Symposium on Computational Geometry, Clear Water Bay, Hong Kong, China, June 12–14, 2000, pages 341–349. ACM, 2000.  doi:10.1145/336154.336221.
  * [22] Jeremy Mann.  Equilateral dimension of Riemannian manifolds with bounded curvature.  Rose-Hulman Undergraduate Mathematics Journal, 14(1):Article 8, 2013\.  URL: https://scholar.rose-hulman.edu/rhumj/vol14/iss1/8/.
  * [23] M. Mazón and T. Recio.  Voronoi diagrams on orbifolds.  Computational Geometry: Theory & Applications, 8(5):219–230, 1997.  doi:10.1016/S0925-7721(96)00017-X.
  * [24] R. E. Miles.  Random points, sets and tessellations on the surface of a sphere.  Sankhyā, Series A, 33:145–174, 1971.  URL: https://www.jstor.org/stable/25049720.
  * [25] S. B. Myers.  Arcs and geodesics in metric spaces.  Transactions of the American Mathematical Society, 57:217–227, 1945.  doi:10.1090/S0002-9947-1945-0011792-9.
  * [26] Hyeon-Suk Na, Chung-Nim Lee, and Otfried Cheong.  Voronoi diagrams on the sphere.  Computational Geometry, Theory and Applications, 23(2):183–194, 2002.  doi:10.1016/S0925-7721(02)00077-9.
  * [27] John Nash.  The imbedding problem for Riemannian manifolds.  Annals of Mathematics, 2nd Ser., 63(1):20–63, 1956.  doi:10.2307/1969989.
  * [28] Frank Nielsen and Richard Nock.  Hyperbolic Voronoi diagrams made easy.  In Bernady O. Apduhan, Osvaldo Gervasi, Andrés Iglesias, David Taniar, and Marina L. Gavrilova, editors, Proceedings of the 2010 International Conference on Computational Science and Its Applications, ICCSA 2010, Fukuoka, Japan, March 23–26, 2010, pages 74–80. IEEE Computer Society, 2010.  doi:10.1109/ICCSA.2010.37.
  * [29] József Solymosi.  Note on integral distances.  Discrete & Computational Geometry, 30(2):337–342, 2003.  doi:10.1007/s00454-003-0014-7.
  * [30] Matthias Weber, David Hoffman, and Michael Wolf.  An embedded genus-one helicoid.  Proceedings of the National Academy of Sciences, 102(46):16566–16568, 2005.  doi:10.1073/pnas.0508008102.