Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Fast and memory-efficient Voronoi diagram construction on triangle meshes

Qin, Yipeng ORCID:, Yu, Hongchuan and Zhang, Jianjun 2017. Fast and memory-efficient Voronoi diagram construction on triangle meshes. Computer Graphics Forum 36 (5) , pp. 93-104. 10.1111/cgf.13248

Full text not available from this repository.


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.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Computer Science & Informatics
Publisher: Wiley
ISSN: 0167-7055
Date of First Compliant Deposit: 10 June 2019
Date of Acceptance: 23 June 2017
Last Modified: 04 Nov 2022 12:30

Citation Data

Cited 4 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item