MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

The Complexity of Geodesic Voronoi Diagrams on Triangulated 2-Manifold Surfaces

Yong-Jin Liu Tsinghua University Kai Tang Hong Kong University

Computational Geometry mathscidoc:1608.09008

Information Processing Letters, 113, 132, 2013
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).
Voronoi diagram; Triangulated surfaces; Combinatorial complexity; Computational geometry
[ Download ] [ 2016-08-19 15:14:23 uploaded by liuyj ] [ 863 downloads ] [ 0 comments ] 
@inproceedings{yong-jin2013the,
  title={The Complexity of Geodesic Voronoi Diagrams on Triangulated 2-Manifold Surfaces},
  author={Yong-Jin Liu, and Kai Tang},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160819151423610237263},
  booktitle={Information Processing Letters},
  volume={113},
  pages={132},
  year={2013},
}
Yong-Jin Liu, and Kai Tang. The Complexity of Geodesic Voronoi Diagrams on Triangulated 2-Manifold Surfaces. 2013. Vol. 113. In Information Processing Letters. pp.132. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160819151423610237263.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved