TY - JOUR
T1 - Efficient computation of clipped Voronoi diagram for mesh generation
AU - Yan, Dongming
AU - Wang, Wen Ping
AU - Lévy, Bruno L.
AU - Liu, Yang
N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: We would like to thank anonymous reviewers for their detailed comments and suggestions which greatly improve the manuscript. We also thank one reviewer who pointed out the Ref. [1]. This work is partially supported by the Research Grant Council of Hong Kong (project no.: 718209 and 718010), the State Key Program of NSFC project (60933008), European Research Council (GOODSHAPE FP7-ERC-StG-205693), and ANR/NSFC (60625202, 60911130368) Program (SHAN Project).
PY - 2013/4
Y1 - 2013/4
N2 - The Voronoi diagram is a fundamental geometric structure widely used in various fields, especially in computer graphics and geometry computing. For a set of points in a compact domain (i.e. a bounded and closed 2D region or a 3D volume), some Voronoi cells of their Voronoi diagram are infinite or partially outside of the domain, but in practice only the parts of the cells inside the domain are needed, as when computing the centroidal Voronoi tessellation. Such a Voronoi diagram confined to a compact domain is called a clipped Voronoi diagram. We present an efficient algorithm to compute the clipped Voronoi diagram for a set of sites with respect to a compact 2D region or a 3D volume. We also apply the proposed method to optimal mesh generation based on the centroidal Voronoi tessellation. Crown Copyright © 2011 Published by Elsevier Ltd. All rights reserved.
AB - The Voronoi diagram is a fundamental geometric structure widely used in various fields, especially in computer graphics and geometry computing. For a set of points in a compact domain (i.e. a bounded and closed 2D region or a 3D volume), some Voronoi cells of their Voronoi diagram are infinite or partially outside of the domain, but in practice only the parts of the cells inside the domain are needed, as when computing the centroidal Voronoi tessellation. Such a Voronoi diagram confined to a compact domain is called a clipped Voronoi diagram. We present an efficient algorithm to compute the clipped Voronoi diagram for a set of sites with respect to a compact 2D region or a 3D volume. We also apply the proposed method to optimal mesh generation based on the centroidal Voronoi tessellation. Crown Copyright © 2011 Published by Elsevier Ltd. All rights reserved.
UR - http://hdl.handle.net/10754/562703
UR - https://linkinghub.elsevier.com/retrieve/pii/S0010448511002351
UR - http://www.scopus.com/inward/record.url?scp=84875949865&partnerID=8YFLogxK
U2 - 10.1016/j.cad.2011.09.004
DO - 10.1016/j.cad.2011.09.004
M3 - Article
SN - 0010-4485
VL - 45
SP - 843
EP - 852
JO - CAD Computer Aided Design
JF - CAD Computer Aided Design
IS - 4
ER -