The Voronoi diagram is a fundamental geometry structure

widely used in various elds, especially in computer graphics and geom-

etry computing. For a set of points in a compact 3D domain (i.e. a nite

3D volume), some Voronoi cells of their Voronoi diagram are in nite, but

in practice only the parts of the cells inside the domain are needed, as

when computing the centroidal Voronoi tessellation. Such a Voronoi dia-

gram con ned to a compact domain is called a clipped Voronoi diagram.

We present an e cient algorithm for computing the clipped Voronoi di-

agram for a set of sites with respect to a compact 3D volume, assuming

that the volume is represented as a tetrahedral mesh. We also describe

an application of the proposed method to implementing a fast method

for optimal tetrahedral mesh generation based on the centroidal Voronoi

tessellation.