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), ... , s(m)} is an element of 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). (C) 2013 Elsevier B.V. All rights reserved.