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 = {s1, s2, . . . , sm} ∈ T, we prove that
the complexity of Voronoi diagram VT (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 VT (S) is O((m + g)n).