کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427543 | 686518 | 2013 | 5 صفحه PDF | دانلود رایگان |
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}∈TS={s1,s2,…,sm}∈T, we prove that the complexity of Voronoi diagram VT(S)VT(S) of S on T is O(mn)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)VT(S) is O((m+g)n)O((m+g)n).
► We show that the complexity of Voronoi diagram VT(S)VT(S) of m point sites S on a triangulated 2-manifold T is O(mn)O(mn) if the genus of T is zero.
► For a genus-g manifold T in which the samples in S are dense enough, we show that the complexity of Voronoi diagram VT(S)VT(S) is O((m+g)n)O((m+g)n).
Journal: Information Processing Letters - Volume 113, Issue 4, 28 February 2013, Pages 132–136