Delaunay triangulations of hyperbolic surfaces
Yde Matthijs Ebbens · 2021
Delaunay triangulations were initially studied for point sets in the Euclidean plane and higher-dimensional Euclidean spaces, but a similar notion exists for Riemannian manifolds [53].More specifically, in the last decade algorithms for computing Delaunay triangulations have been extended to point sets in hyperbolic spaces [22,13,44]. ix x Previous workIn previous work, Delaunay triangulations of hyperbolic surfaces were mostly studied from an algorithmic point of view.For instance, Bowyer's incremental algorithm [19] for computing Delaunay triangulations of point sets in the Euclidean plane was generalized to hyperbolic surfaces and implemented for the Bolza surface [15,16,45].Lawson's flip algorithm [52] has also been shown to generalize Even though there is a generalization of Bowyer's algorithm to arbitrary hyperbolic surfaces in the literature [15], the validity condition in this generalization depends on the value of the systole, which is not known in general.There exists an algorithm to compute the systole of a given hyperbolic surface [2], but since the complexity of this algorithm has not been analyzed, it is not clear whether it can be used in practice.Therefore, one part of our extension of Bowyer's algorithm to Publications Several parts of this thesis have previously appeared as conference papers or