Surface mesh shortest path using edge lengths instead of vertex coordinates

[SimonMarynissen]

Issue Details

The class CGAL::Surface_mesh_shortest_path requires that the underlying FaceListGraph supplies a point (coordinates) for each vertex. However, in my particular use case, I only have information of the edge lengths of the triangulation. It's perfectly possible to use this information instead in the algorithm used in calculating the shortest paths.

Some more information about my use case: Alexandrov's uniqueness theorem states that each polyhedral metric (with some extra properties) specifies a unique convex polyhedron, but the theorem gives no algorithm to construct this polyhedron, but a (sufficiently) efficient algorithm is given by Kane, Price, and Demaine; in their algorithm a Voronoi diagram is constructed on a polyhedral metric (which is given as a triangulation with the edge lengths provided, but no vertex coordinates). In their paper, they use a slightly revised version of the algorithm of Mitchell, Mount, and Papadimitriou to construct this Voronoi diagram, however, the algorithm by Xin and Wang (on which CGAL::Surface_mesh_shortest_path is based) has better complexity guarantees. As I would like to code the algorithm for Alexandrov's uniqueness theorem, I would like to calculate shortest paths on triangulated polyhedral surfaces without vertex coordinates.

Can this be done easily with the current code structure of CGAL::Surface_mesh_shortest_path, or does it require substantial code changes? Any pointers would be appreciated. I would also be happy to contribute it back to CGAL.

[afabri]

We had a look and it would be rather non-trivial to do.

[SimonMarynissen]

That's unfortunate, any pointers on what needs changing?

[MaelRL]

We do not have any structure to manipulate graphs defined with edge lengths only, and the current shortest path code builds a number of geometric primitives such as triangles and distances directly from point coordinates.

The algorithm uses window propagation with local mesh unfolding so it should be possible to do it with edge lengths only, but it would be a significant rewrite.