Non-Euclidean Erdős-Anning Theorems

Eppstein, David

doi:10.4230/LIPIcs.SoCG.2025.46

Non-Euclidean Erdős–Anning Theorems

David Eppstein University of California, Irvine, CA, USA

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.

Keywords and phrases:

integer distances, additively weighted Voronoi diagrams, convex distance functions, Riemannian manifolds, geodesic distance

Funding:

David Eppstein: Research supported in part by NSF grant CCF-2212129.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry

Editors:

Oswin Aichholzer and Haitao Wang

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Many incidence properties of lines or curves, seemingly mysterious on their own, become obvious when viewed through the lens of computational geometry, where the curves may be features of Voronoi diagrams or related constructions. Thus, for instance, to see that the three perpendicular bisectors of a triangle’s sides meet at a single point, observe that these bisectors contain the edges of the Voronoi diagram of the triangle vertices, and these Voronoi edges meet at the Voronoi vertex. In this work we apply the same principle to the Erdős–Anning theorem on integer distances in the plane, conventionally proven using the algebraic intersection properties of hyperbolae. By reinterpreting these hyperbolae and their intersection points as the cell boundaries and vertices of additively-weighted Voronoi diagrams, and by analyzing these diagrams geometrically and topologically rather than algebraically, we greatly generalize this theorem, to several wide classes of two-dimensional metric spaces. In doing so, we resolve a 1983 question of Richard Guy on the equilateral dimension of Riemannian manifolds, the maximum number of points that can be placed at equal distances from each other in these spaces.

The Erdős–Anning theorem states that every point set in the Euclidean plane with integer distances must be either collinear or finite [1, 9]. 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)$ [25], and if in addition it is non-collinear its number of points is $D^{O(1/\log\log D)}$ [11]. 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 [10, 13].

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 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 that analogous statements are untrue for some metrics. For the $L_{1}$ or $L_{\infty}$ distances in the plane, 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 3)
For any two-dimensional complete Riemannian manifold of finite genus $g$ , every point set with integer distances must either be finite or be contained in a geodesic (a locally-shortest curve) that contains every shortest curve between pairs of the points. If some three 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 4)
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 be contained in a geodesic that contains every shortest curve between pairs of the points. If some three 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 5)

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 [12], on the equilateral dimension of Riemannian manifolds, the maximum number of points at unit distance from each other in these manifolds. Guy asked whether the equilateral dimension could be bounded by a function of dimension. For complete Riemannian 2-manifolds of bounded genus, we bound the equilateral dimension by a function of the genus (Corollary 12) 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}$ , we show that the equilateral dimension is unbounded (Example 6 and Example 7).

For space reasons we defer many lemmas and other material to the full version at https://arxiv.org/2401.06328.

2 Preliminaries: Voronoi diagrams and star-shaped cells

A Voronoi diagram of a finite set of point sites in a metric space $(X,d)$ subdivides the space according to which site is closest. 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 whose 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 [6, 15, 17], for points on a sphere [21, 3, 23], for points in the hyperbolic plane [8, 24, 4], orbifolds [20], and for more general Riemannian manifolds [18]. Additively weighted Voronoi diagrams are also a standard concept [5, 16], and confusingly, are sometimes called hyperbolic Dirichlet tessellations despite their use of Euclidean distance [2], because their cells are bounded by hyperbolas (the same hyperbolas from the Erdős–Anning proof). We did not find works combining additive weights and non-Euclidean distances.

Figure 1: 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 $p q$ 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 Figure 1. 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 [6]. 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].

3 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 [6]:

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. Convex distance functions define geodesic metric 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.

In unweighted Voronoi diagrams of strictly convex distance functions, every cell is a topological disk (or the whole space) with its site in its interior. However, additively weighted Voronoi diagrams may have additional complications, which we examine more carefully in the full version. In brief: A site may have zero or negative distance to another site, and therefore belong to the cell of another site; we call such sites degenerate. The Voronoi cell of a degenerate site may be empty, a single point, or a line segment or ray extending away from the site in the direction opposite its nearest non-degenerate neighbor. The cells of non-degenerate sites are strictly star-shaped with respect to their sites, interior-disjoint, and cover the plane. From these properties we prove:

Lemma 1.

For the additively weighted Voronoi diagram of three non-collinear points, the three cells have at most two points of common intersection.

The proof is a case analysis that considers how many sites are degenerate. The two degenerate cells of two degenerate sites lie on rays diverging from the non-degenerate site, and cannot intersect. With one degenerate site, there can be only one point of common intersection, the degenerate site (if its cell is a single point) or the opposite endpoint of its line segment cell. The main case has no degenerate sites. If there could be three points of common intersection, the line segments connecting these points to the three sites would lie entirely within the cells of their sites, and could not cross. Therefore, these segments would form a planar drawing of the nonplanar graph $K_{3,3}$ , a contradiction.

3.1 Erdős–Anning theorems for strict convex distance functions

Theorem 2.

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(s_{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 by Lemma 1, 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}$ . $\hfill\blacktriangleleft$

The following generalization of the Erdős–Anning theorem follows immediately:

Theorem 3.

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 apply Theorem 2. $\hfill\blacktriangleleft$

3.2 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 [25] for Euclidean distance.

Theorem 4.

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.

We may assume without loss of generality that the unit ball of the given distance function $d$ is contained in a Euclidean unit circle. For, if it does not, let $\xi$ be the maximum Euclidean distance from the origin to any point of the unit $d$ -ball, and scale both $S$ and $d$ by $1/\xi$ , leaving distances between the scaled points unchanged and allowing the $d$ -ball to fit within a Euclidean unit circle. Let $\rho$ be the minimum Euclidean distance from the origin of the unit circle of $d$ ; note that, if we treat the distance function as fixed, then $\rho$ is a constant. Then the function measured by $d$ is lower bounded by the Euclidean distance, and upper bounded by $\tfrac{1}{\rho}$ times the Euclidean distance. From the lower bound on $d$ , the Euclidean diameter of $S$ is at most its $d$ -diameter, $D$ .

Figure 2: Figure for the proof of Theorem 4: 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$ , and 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 Figure 2 for an example.) We distinguish two cases:

$\blacksquare$

If $p$ is on the boundary of $B$ , as shown in Figure 2, 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)$ (larger than the Euclidean length by at most the constant factor $\tfrac{1}{\rho}$ ). For this distance to be a nonzero integer, $n$ must be $O(D)$ .
$\blacksquare$

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}$ . Therefore, the Euclidean distance from $s_{1}$ to $p$ is at least half the Euclidean distance from $s_{1}$ to $s_{3}$ . Combining this inequality with the area of the triangle and the $\tfrac{1}{\rho}$ factor by which $d$ can increase over Euclidean distance gives the bound $d(s_{1},s_{2})\cdot d(s_{1},s_{3})=O(D^{2}/n)$ . It follows from Theorem 2 that $n=O(D^{2}/n)$ and therefore that $n=O(D)$ .

$\hfill\blacktriangleleft$

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.

4 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. 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 more 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 [14], every complete Riemannian manifold has a shortest curve between every two points. Thus, these are geodesic metric spaces.

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.

4.1 Examples

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 [26]. 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.

Refer to caption — Figure 3: 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. Let $S$ consist of one point per sphere, for spheres small enough that all distances within one sphere are less than $\tfrac{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$ , 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 [12]. A positive answer was known only for the case of complete Riemannian manifolds of bounded curvature [19]. 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 12).

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

In the full version we prove properties of additively weighted Voronoi diagrams for Riemannian manifolds analogous to those of convex distance functions, culminating in a bound of $2g+2$ on the number of intersections of the cells of three sites with none of the three belonging to a geodesic between the other two.

4.2 Erdős–Anning theorems for Riemannian manifolds

Theorem 8.

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 our bound on triple points of Voronoi diagrams from the full version, the proof is the same as for Theorem 2. 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 9.

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 two rays $R_{2}$ and $R_{3}$ in this system of rays contain 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 a shortest curve from $s_{2}$ to $s_{3}$ would follow $R_{2}$ from $s_{2}$ to $s_{1}$ and then follow $R_{3}$ 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. $\hfill\blacktriangleleft$

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 8 with Lemma 9 gives us the following generalization of the Erdős–Anning theorem:

Theorem 10.

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 there is a single geodesic of the manifold containing all points of $S$ and connecting each pair of points by a shortest curve.

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

Theorem 11.

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 8. 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$ . $\hfill\blacktriangleleft$

Corollary 12.

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

5 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 cone point of negative curvature can be an obstacle to Erdős–Anning theorems. For concreteness, in this section we usually define a convex surface to mean the boundary of a convex subset of $\mathbb{R}^{3}$ with nonempty interior. However, we also allow a special case, which can be thought of as the limit of convex cylinders as the cylinder height goes to zero: the double covering of a convex subset $K$ of $\mathbb{R}^{2}$ , obtained by gluing two copies of $K$ at corresponding boundary points. For instance, the Euclidean plane is a convex surface in the first of these two senses: 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 being either boundaries of convex bounded subsets of $\mathbb{R}^{3}$ or double covers of convex bounded subsets of $\mathbb{R}^{2}$ [7]. We include double covers in our definition of convex surfaces to be consistent with this result of Pogorelov, but we do not require the convex sets from which they are defined to be bounded. 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 [22], 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).

Figure 4: A solid cone.

The boundary of a (bounded) solid cone (Figure 4) 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 13.

For every point $p$ on a convex surface, the disks of radius $r$ centered on that point, in the limit as $r\to 0$ , approach a cone for which $p$ either has angular deficit zero ( $p$ is locally Euclidean) or a well-defined positive angular deficit ( $p$ is locally 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$ . $\hfill\blacktriangleleft$

We defer the detailed analysis of Voronoi diagrams for these metrics to the full version.

5.1 Erdős–Anning theorems for convex surfaces

Theorem 14.

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 2 and Theorem 8, substituting the properties of additive Voronoi diagrams for convex surfaces in place of the corresponding properties of the diagrams for convex distance functions and Riemannian manifolds. $\hfill\blacktriangleleft$

Lemma 15.

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 9, again substituting the properties of Voronoi diagrams on these surfaces. $\hfill\blacktriangleleft$

Theorem 16.

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 10, again substituting the properties of Voronoi diagrams on these surfaces. $\hfill\blacktriangleleft$

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

Figure 5: Lemma 17: a short path connecting two of three points separated by a convex set.

Lemma 17.

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$ . The three lines form a triangle or unbounded three-sided region containing $U$ ; if all three points lie its sides, one of its internal angles is $\geq 60^{\circ}$ , and the curve connecting two points through this angle has length at most twice the distance between the points (Figure 5; 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. $\hfill\blacktriangleleft$

Lemma 18.

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

Proof.

Let the set of points be $S$ , and let the convex surface be the boundary of a set $K$ (or the double cover of a set $K$ ), embedded in $\mathbb{R}^{3}$ . By assumption, $S$ lies within a ball $B$ 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 let $\Box$ denote the set of cubes in this grid whose intersection with $B\cap K$ is non-empty and includes at least one non-vertex point of the cube. Each point in $S$ is contained in at least one cube $C\in\Box$ . This cube $C$ must touch (at least at a corner) a grid cube that is outside $\Box$ , because if all eight cubes corner-adjacent to $C$ belonged to $\Box$ , the intersection points of these eight cubes with $B\cap K$ would have a convex hull that entirely encloses $C$ , preventing $C$ from containing any boundary points of $K$ . Therefore, $C$ is within $O(1)$ grid positions of a boundary square of the union of cubes $\cup\Box$ . But $\cup\Box$ is orthogonally convex – any axis-parallel line can cross only two boundary squares (one in each direction) – so it has $O(n)$ boundary squares. Therefore there are also $O(n)$ cubes near these squares that contain points of $S$ . By choosing the grid size appropriately, we can adjust the constant factors in this $O(n)$ bound and ensure that fewer than $n/2$ cubes contain points of $S$ . With this adjustment, some cube $C\in\Box$ , of side length $O(D/\sqrt{n})$ , contains at least three points of $S$ . We consider two cases:

$\blacksquare$

If the convex surface is non-degenerate (it bounds a convex set with non-empty interior), then by Lemma 17, 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.
$\blacksquare$

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 within $C$ by a geodesic segment of length $O(D/\sqrt{n})$ .

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

The example of a square grid of $\sqrt{n}\times\sqrt{n}$ points on a flat plane, scaled to have diameter $D$ , shows that Lemma 18 is tight.

Theorem 19.

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 18. We distinguish two cases:

$\blacksquare$

Suppose that all triples of points in $S$ that include both $p$ and $q$ belong to shortest curves. Each point in $S$ 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, two rays contain all remaining points in $S$ , and these points lie at integer spacing along these two rays, giving $O(D)$ points in $S$ in total.
$\blacksquare$

Otherwise, some point $r$ does not lie on a shortest curve with $p$ and $q$ . By Theorem 14, 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.

$\hfill\blacktriangleleft$

6 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 [15]. 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 11 and Theorem 19.

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] 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.
[6] 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.
[7] Robert Connelly. Convex Polyhedra by A. D. Alexandrov. SIAM Review, 48(1):157–160, March 2006. doi:10.1137/SIREAD000048000001000149000001.
[8] 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.
[9] Paul Erdős. Integral distances. Bulletin of the American Mathematical Society, 51:996, 1945. doi:10.1090/S0002-9904-1945-08490-0.
[10] 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/.
[11] Rachel Greenfeld, Marina Iliopoulou, and Sarah Peluse. On integer distance sets. Electronic preprint arxiv:2401.10821, 2024.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
[16] 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.
[17] 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.
[18] 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.
[19] 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/.
[20] 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.
[21] 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.
[22] 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.
[23] 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.
[24] 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.
[25] József Solymosi. Note on integral distances. Discrete & Computational Geometry, 30(2):337–342, 2003. doi:10.1007/s00454-003-0014-7.
[26] 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.

[bib.bib1] [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.

[bib.bib2] [2] Peter F. Ash and Ethan D. Bolker. Generalized Dirichlet tessellations. Geometriae Dedicata, 20(2):209–243, 1986. doi:10.1007/BF00164401.

[bib.bib3] [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.

[bib.bib4] [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.

[bib.bib5] [5] 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.

[bib.bib6] [6] 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.

[bib.bib7] [7] Robert Connelly. Convex Polyhedra by A. D. Alexandrov. SIAM Review, 48(1):157–160, March 2006. doi:10.1137/SIREAD000048000001000149000001.

[bib.bib8] [8] 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.

[bib.bib9] [9] Paul Erdős. Integral distances. Bulletin of the American Mathematical Society, 51:996, 1945. doi:10.1090/S0002-9904-1945-08490-0.

[bib.bib10] [10] 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/.

[bib.bib11] [11] Rachel Greenfeld, Marina Iliopoulou, and Sarah Peluse. On integer distance sets. Electronic preprint arxiv:2401.10821, 2024.

[bib.bib12] [12] 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.

[bib.bib13] [13] 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.

[bib.bib14] [14] 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.

[bib.bib15] [15] 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.

[bib.bib16] [16] 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.

[bib.bib17] [17] 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.

[bib.bib18] [18] 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.

[bib.bib19] [19] 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/.

[bib.bib20] [20] 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.

[bib.bib21] [21] 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.

[bib.bib22] [22] 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.

[bib.bib23] [23] 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.

[bib.bib24] [24] 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.

[bib.bib25] [25] József Solymosi. Note on integral distances. Discrete & Computational Geometry, 30(2):337–342, 2003. doi:10.1007/s00454-003-0014-7.

[bib.bib26] [26] 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.

Non-Euclidean Erdős–Anning Theorems

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

2 Preliminaries: Voronoi diagrams and star-shaped cells

3 Convex distance functions

Lemma 1.

3.1 Erdős–Anning theorems for strict convex distance functions

Theorem 2.

Proof.

Theorem 3.

Proof.

3.2 Diameter bounds

Theorem 4.

Proof.

4 Riemannian manifolds

4.1 Examples

Example 5.

Example 6.

Example 7.

4.2 Erdős–Anning theorems for Riemannian manifolds

Theorem 8.

Lemma 9.

Proof.

Theorem 10.

Theorem 11.

Proof.

Corollary 12.

5 Convex surfaces

Lemma 13.

Proof.

5.1 Erdős–Anning theorems for convex surfaces

Theorem 14.

Proof.

Lemma 15.

Proof.

Theorem 16.

Proof.

Lemma 17.

Proof.

Lemma 18.

Proof.

Theorem 19.

Proof.

6 Discussion

References