Fast and Memory-Efficient Voronoi Diagram Construction on Triangle Meshes

Eurographics DL Repository

Show simple item record Qin, Yipeng en_US Yu, Hongchuan en_US Zhang, Jiangjun en_US
dc.contributor.editor Bærentzen, Jakob Andreas and Hildebrandt, Klaus en_US 2017-07-02T17:37:48Z 2017-07-02T17:37:48Z 2017
dc.identifier.issn 1467-8659
dc.description.abstract Geodesic based Voronoi diagrams play an important role in many applications of computer graphics. Constructing such Voronoi diagrams usually resorts to exact geodesics. However, exact geodesic computation always consumes lots of time and memory, which has become the bottleneck of constructing geodesic based Voronoi diagrams. In this paper, we propose the window-VTP algorithm, which can effectively reduce redundant computation and save memory. As a result, constructing Voronoi diagrams using the proposed window-VTP algorithm runs 3-8 times faster than Liu et al.'s method [LCT11], 1.2 times faster than its FWP-MMP variant and more importantly uses 10-70 times less memory than both of them. en_US
dc.publisher The Eurographics Association and John Wiley & Sons Ltd. en_US
dc.subject I.3.5 [Computer Graphics]
dc.subject Computational Geometry and Object Modeling
dc.subject Curve
dc.subject surface
dc.subject solid
dc.subject and object representations
dc.title Fast and Memory-Efficient Voronoi Diagram Construction on Triangle Meshes en_US
dc.description.seriesinformation Computer Graphics Forum
dc.description.sectionheaders Meshing
dc.description.volume 36
dc.description.number 5
dc.identifier.doi 10.1111/cgf.13248
dc.identifier.pages 093-104

Files in this item

Pay-Per-View via TIB Hannover:

Try if this item/paper is available.

This item appears in the following Collection(s)

  • 36-Issue 5
    Geometry Processing 2017 - Symposium Proceedings

Show simple item record

Search Eurographics DL


My Account