Polyline-sourced geodesic Voronoi diagrams on triangle meshes

Chun-Xu Xu Tsinghua University Yong-Jin Liu Tsinghua University Qian Sun Nanyang Technological University Jinyan Li University of Technology Sydney Ying He Nanyang Technological University

Computational Geometry mathscidoc:1608.09006

Computer Graphics Forum, 33, (7), 2014.11
This paper studies the Voronoi diagrams on 2-manifold meshes based on geodesic metric (a.k.a. geodesic Voronoi diagrams or GVDs), which have polyline generators. We show that our general setting leads to situations more complicated than conventional 2D Euclidean Voronoi diagrams as well as point-source based GVDs, since a typical bisector contains line segments, hyperbolic segments and parabolic segments. To tackle this challenge, we introduce a new concept, called local Voronoi diagram (LVD), which is a combination of additively weighted Voronoi diagram and line-segment Voronoi diagram on a mesh triangle. We show that when restricting on a single mesh triangle, the GVD is a subset of the LVD and only two types of mesh triangles can contain GVD edges. Based on these results, we propose an efficient algorithm for constructing the GVD with polyline generators. Our algorithm runs in O(nNlogN) time and takes O(nN) space on an n-face mesh with m generators, where N = max{m,n}. Computational results on real-world models demonstrate the efficiency of our algorithm.
No keywords uploaded!
[ Download ] [ 2016-08-19 14:46:44 uploaded by liuyj ] [ 826 downloads ] [ 0 comments ]
  title={Polyline-sourced geodesic Voronoi diagrams on triangle meshes},
  author={Chun-Xu Xu, Yong-Jin Liu, Qian Sun, Jinyan Li, and Ying He},
  booktitle={Computer Graphics Forum},
Chun-Xu Xu, Yong-Jin Liu, Qian Sun, Jinyan Li, and Ying He. Polyline-sourced geodesic Voronoi diagrams on triangle meshes. 2014. Vol. 33. In Computer Graphics Forum. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160819144644462364261.
Please log in for comment!
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved