Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface
This work addresses a computational geometry problem for researchers and practitioners dealing with surface representations, offering a method to pre-process surfaces for tasks like shortest path computation and isometry checking, though it is incremental as it builds on prior results about bounded happiness in Delaunay triangulations.
The paper tackles the problem of computing the intrinsic Delaunay triangulation for closed polyhedral surfaces represented by triangular portalgons, providing an algorithm with polynomial time complexity in the number of triangles and the logarithm of the aspect ratio, and proving that the dependency on the aspect ratio is unavoidable.
Every surface that is intrinsically polyhedral can be represented by a portalgon: a collection of polygons in the Euclidean plane with some pairs of equally long edges abstractly identified. While this representation is arguably simpler than meshes (flat polygons in R3 forming a surface), it has unbounded happiness: a shortest path in the surface may visit the same polygon arbitrarily many times. This pathological behavior is an obstacle towards efficient algorithms. On the other hand, Löffler, Ophelders, Staals, and Silveira (SoCG 2023) recently proved that the (intrinsic) Delaunay triangulations have bounded happiness. In this paper, given a closed polyhedral surface S, represented by a triangular portalgon T, we provide an algorithm to compute the Delaunay triangulation of S whose vertices are the singularities of S (the points whose surrounding angle is distinct from 2pi). The time complexity of our algorithm is polynomial in the number of triangles and in the logarithm of the aspect ratio r of T. Within our model of computation, we show that the dependency in log(r) is unavoidable. Our algorithm can be used to pre-process a triangular portalgon before computing shortest paths on its surface, and to determine whether the surfaces of two triangular portalgons are isometric.