The complexity of geodesic Voronoi diagrams on triangulated 2-manifold surfaces

We study the combinatorial complexity of Voronoi diagram of point sites on a general triangulated 2‐manifold surface, based on the geodesic metric. Given a triangulated 2‐manifold T of n faces and a set of m point sites $S=\{s_1,s_2,\dots ,s_m\}\in T$ , we prove that the complexity of Voronoi diagram $V_T(S)$ of S on T is $O(mn)$ if the genus of T is zero. For a genus‐g manifold T in which the samples in S are dense enough and the resulting Voronoi diagram satisfies the closed ball property, we prove that the complexity of Voronoi diagram $V_T(S)$ is $O((m+g)n)$ .