The Complexity of Geodesic Voronoi Diagrams on Triangulated 2-Manifold Surfaces
Published in Information Processing Letters, 2013
Abstract: 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 $\mathcal{T}$ of $n$ faces and a set of $m$ point sites $S={s_1,s_2,…,s_m}$, we prove that the complexity of Voronoi diagram $V_T(S)$ of $S$ on $\mathcal{T}$ is $O(mn)$ if the genus of $\mathcal{T}$ is zero. For a genus-g manifold $\mathcal{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)$.
Recommended citation: Yong-Jin Liu, Kai Tang (2013) The Complexity of Geodesic Voronoi Diagrams on Triangulated 2-Manifold Surfaces. Information Processing Letters, Vol. 113, No. 4, pp. 132-136, 2013.