Fast and Memory-Efficient Voronoi Diagram Construction on Triangle Meshes

dc.contributor.authorQin, Yipengen_US
dc.contributor.authorYu, Hongchuanen_US
dc.contributor.authorZhang, Jiangjunen_US
dc.contributor.editorBærentzen, Jakob Andreas and Hildebrandt, Klausen_US
dc.date.accessioned2017-07-02T17:37:48Z
dc.date.available2017-07-02T17:37:48Z
dc.date.issued2017
dc.description.abstractGeodesic 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.description.number5
dc.description.sectionheadersMeshing
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume36
dc.identifier.doi10.1111/cgf.13248
dc.identifier.issn1467-8659
dc.identifier.pages093-104
dc.identifier.urihttps://doi.org/10.1111/cgf.13248
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf13248
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectI.3.5 [Computer Graphics]
dc.subjectComputational Geometry and Object Modeling
dc.subjectCurve
dc.subjectsurface
dc.subjectsolid
dc.subjectand object representations
dc.titleFast and Memory-Efficient Voronoi Diagram Construction on Triangle Meshesen_US
Files
Collections