The following treats the problem of computing distances and shortest geodesics (the generalization of straight lines to general manifolds) on polyhedral metrics, given only the intrinsic surface in the form of a graph that represents the 1-skeleton of the polyhedron. That is, no reference is made to any embedding in 3D. This is a necessary step towards calculating electron repulsion on carbon manifold directly from their graphs, without the need for an expensive optimization step to find their 3D geometries.

The algorithm I derive is specialized to
simplical metrics, i.e., surfaces with faces that are equilateral
triangles. However, by the method we describe in
Wirz,
Schwerdtfeger, and Avery 2017, *Naming Polyhedra
by General Face-Spirals*, this can be extended through a
leapfrog transformation to general polyhedral metrics.

The code is included in our open source fullerene analysis program Fullerene, and used in the experimental methods for direct embedding calculations, as well as the pilot DFT calculations directly on the manifold. However, the work is not yet published: A paper is in preparation, and I ask the grant referees to not share any of this work yet.

Unlike the case of a sphere, there are in general many geodesics connecting any two points, and three points do not define a unique triangle. The figure here shows two straight lines of different lengths that connect the same two points.

Figure 1 shows two geodesics lines *of different lengths* that connect the same two points,
corresponding to two different cuts, each unfolded into the Eisenstein plane as a straight line.
One goes through $v$, the other goes around it, but is shorter.

Generally, the number of geodesics that connect any two points on
a polyhedral metric surface grows *exponentially* in the
number of cone-points, i.e., the vertices that induce its Gaussian
curvature. For simplical surfaces (that have equilateral triangle
faces), these are the vertices of degree ≠ 6 (dually, the
non-hexagon faces for cubic graph surfaces).
Further, the bumpy, curved surfaces do not admit any global, isometric 2D-coordinate system,
i.e., we cannot find a *single, flat 2D coordinate system* for the whole bumpy, curved surface,
making geometry difficult.

**However,**
pairs of *adjacent simplices* share a Cartesian
coordinate system.
Outside the pair, the coordinate system is invalid (and geometric operations
will yield gibberish if neighbouring a cone point), but
*inside* such a pair, lengths and angles
are "flat", and we can calculate them as we are used to from Cartesian coordinate systems.

The algorithm below exploits this fact for calculating geodesics
through *overlapping patches* of Cartesian coordinate systems.

The algorithm rests on a lemma stating that shortest geodesics can be understood to be
*piecewise linear* in the sense that the sequence of
faces that a shortest geodesic passes through can be cut out and
laid out flat in the Eisenstein plane (isometrically, i.e.,
without changing the surface distances). The geodesic can then
be drawn as a finite sequence of straight lines, each never
crossing through a cone point singularity, but possibly ending
at one. In addition, for convex polyhedral metrics (such as
those of fullerene surfaces), shortest geodesics consist of
a *single* "straight line". Note, however, that the concept of
"straight line" is not straight forward, as illustrated in Figure 1.

More precisely, geodesics are composed of *simple paths*, defined as follows:

**Definition, Simple Path:**
A *simple* path is one that does not pass through
cone points (vertices with degree ≠ 6) except at its end points.

**Lemma 1: Shortest geodesics are piecewise simple.**

Proof.

Proof.

Proof.

Convex polyhedral metrics are characterized by having no non-convex cone-points, i.e., vertices with degree > 6, i.e., all cone-points are convex. By Lemmas 1 and 2 it follows that a shortest geodesics on a convex polyhedral metric must be simple.Thus, we can solve the general problem by solving the simple-path connection problem. For convex polyhedral metrics, this is the end, yielding shortest geodesics and distances. Non-convex metrics require one extra step: computing shortest paths in the "shortest simple-paths" connection graph (weighted by the shortest simple path lengths). In my implementation, I simply compute all-pairs-shortest-paths using matrix-multiplication in the min/+-semiring, a standard method for APSP in dense weighted graphs, but any other standard method can be used.

Because shortest geodesics are piecewise simple, we can reduce the problem to that of finding *shortest simple paths*,
and combining these to form the shortest geodesics.

The following two observations are each somewhat trivial, but together they point towards an algorithm that efficiently finds the shortest simple paths:

**Observation 1:** The surface distance $d(u,v)$ between two vertices $u$ and $v$ is bounded from above by $D(u,v)$, the
graph-distance (along edges) between $u$ and $v$.

**Observation 2:** Let $M = \max_v D(u,v)$ be the largest
graph distance from $u$. Then a shortest simple path
$u$—$v$ can be represented as a straight line, drawn on a
triangle strip in the Eisenstein plane. The path-segment in the overlapping coordinate systems
between successive triangle pairs uniquely determines the line's continuation in the next coordinate system.
When $u$ is given
Eistenstein coordinate $(0,0)$, then $v$ has coordinates
$(a,b)$, where $|(a,b)| = \sqrt{a^2+ab+b^2} \le M$.

**Observation 3:**
Conversely, if we can "draw" an Eisenstein line $(0,0)$—$(a,b)$ from vertex $u$, and by "drawing" it reach vertex $v$,
then $d(u,v)^2 \le a^2 + ab + b^2$.

**Observation 4:** We can "draw" an Eisenstein line to
$(a,b)$ relative to $u$ and find the vertex $v$ at its endpoint
by successively laying down the triangles in the Eisenstein
plane, each time the line crosses an edge into a new face. The
result will be a straight line drawn on the laid down triangles in the Eisenstein plane
(but curved in an isometric 3D embedding of the surface).

From this, we can formulate an outline of an algorithm:

↦ |