Bowyer-Watson Algorithm for Delaunay Triangulation on Hyperbolic Surfaces

Overview & Synopsis

The well known Bowyer-Watson algorithm constructs the Delaunay triangulation of a point set in the plane incrementally. The restoration of the Delaunay property in the conflict zone of an inserted point is non-ambiguous since this zone is a topological disk. This property no longer holds on a surface with non-trivial topology. We propose an extension of the Bowyer-Watson algorithm to hyperbolic surfaces. Our algorithm uses a thin/thick decomposition of the hyperbolic surface. It first computes an initial point set together with its Delaunay triangulation via an epsilon-net sampling of the surface. The insertion procedure in the thick part of the surface is as in the original algorithm in the plane. The insertion in the thin part differs to overcome the possibly non-trivial topology of the conflict zone.