Abstract

This paper shows how Voronoi diagrams and their dual De- launay complexes, defined with geodesic distances over 2D Reimannian manifolds, can be used to solve two important problems encountered in computer vision and graphics. The first problem studied is perceptual grouping which is a curve reconstruction problem where one should com- plete in a meaningful way a sparse set of noisy curves. From this latter curves, our grouping algorithm first designs an anisotropic tensor field that corresponds to a Reimannian metric. Then, according to this met- ric, the Delaunay graph is constructed and pruned in order to correctly link together salient features. The second problem studied is planar do- main meshing, where one should build a good quality triangulation of a given domain. Our meshing algorithm is a geodesic Delaunay refine- ment method that exploits an anisotropic tensor field in order to locally impose the orientation and aspect ratio of the created triangles.