Computing distances

[videlec]

It is desirable to implement distances for points in a Euclidean or hyperbolic surface.

• J. S. B. Mitchell, D. M. Mount and C. H. Papadimitriou "The Discrete Geodesic Problem" (1987)

Dependencies

• Segments WIP: segments and paths #333
• Paths WIP: segments and paths #333
• shortest path(s)

[saraedum]

This is implemented in #213.

[saraedum]

It is desirable to implement distances for points in a Euclidean or hyperbolic surface.

* [J. S. B. Mitchell, D. M. Mount and C. H. Papadimitriou "The Discrete Geodesic Problem" (1987)](https://epubs.siam.org/doi/10.1137/0216045)

Their algorithm runs in $O(E^2 log E)$, however, that algorithm only applies to polyhedra. I don't see how the idea can be rescued for say translation surfaces. There are statements such as Lemma 4.1 which I think are crucial to the construction and don't hold.

An optimal path $p(x)$ to a point $x\in e$ [e is an edge] passes through the interior of at most one face containing $x$.

The implementation that I put in before you had posted that reference is somewhat naive and runs in $O(V^4)$ (maybe somehow $O(V^3)$ with better analysis of the runtime).

[videlec]

Indeed, the statements in the article looks very wrong (or I misunderstand the definitions)! If the surface is "reasonable" but the triangulation is "crazy", then there is no way you can achieve $O(E^2 log E)$.

They seem to consider a "restricted" setting where they assume that their surface is embedded in $\mathbb{R}^3$ and the faces are the faces of the polyhedron. In that setting I believe that faces can not be too crazy.

[saraedum]

So, the only viable approach seems to be to reduce the problem to a saddle connection search with good upper bounds. This is what I did in #213 which is a lot of Floyd which is why I said initially $O(V^4)$ but actually it has a saddle connection search in there and that cannot be immediately bounded by something that only depends on the combinatorics of the surface.

[videlec]

There might be some optimization in the saddle connection search. Namely, the shortest paths will only use a finite subset of saddle connections and ideally we want to enumerate only those. Some challenges and thoughts

• Characterize geometrically saddle connections that are used in some shortest paths (I believe that they correspond to the ones that do not cross the boundary of the Voronoi cell based at a given vertex).
• Find good bounds for their numbers, I think that it is reasonable to expect $\leq n^2$ where $n$ is the number of vertices
• Understand whether there is a way to tweak the saddle connection search to enumerate only those (probably building the Voronoi cell at each vertex, there might be ways to share information between vertices)
• Note that if there is a single vertex, then saddle connections are useless. But given a pair $(x,y)$ the shortest path might pass through the singularity.
• Somehow one needs to understand the set of pairs $(x,y) \in S \times S$ where there are two shortest paths from $x$ to $y$. On the complement of this set, the combinatorics of the shortest path is fixed.

[saraedum]

On a much more elementary level, the length of a shortest path is a sum of square roots. It's annoying to even compare the lengths of two paths…

[saraedum]

Also, we do not have segments in sage-flatsurf yet. Only the StraightLineTrajectory, so it's a bit hard to represent such a shortest path. I'd say that essentially each segment should be a tangent vector + holonomy.

[videlec]

On a much more elementary level, the length of a shortest path is a sum of square roots. It's annoying to even compare the lengths of two paths…

I think it would be good to switch from e-antic to flint via flintlib/flint#1848 (though this is lacking the C++ interface). Then one could use one of the two Frederik implementations of AA.