Anisotropic Voronoi Diagrams and Delaunay Triangulations.
Speaker: Guillermo D. Canas , School of Engineering and Applied Sciences, Harvard University
Date: March 2 2011
Time: 4:30PM to 5:30PM
Location: Star Sem Rm, Stata D463
Host: Lorenzo Rosasco, Istituto Italiano di Tecnologia; CBCL, MIT
Contact: Kathleen Sullivan, 617-253-0551, kdsulliv@mit.edu
Relevant URL: http://cbcl.mit.edu/
ABSTRACT: Voronoi diagrams and Delaunay triangulations are used in areas as diverse as data compression, FEM simulation, computer graphics, wireless networks, and function approximation. Due to their wide application, great interest exists in anisotropic extensions (defined over Euclidean space endowed with a continuously-varying metric tensor). However, little is known on how to generalize them in a way that they remain efficient to compute and have theoretical guarantees of well-behaved-ness.
We present sufficient conditions under which the two best-known existing
approximate anisotropic Voronoi diagrams are well behaved, in any number of dimensions. These conditions arise naturally in the context of optimization and approximation, and algorithms already exist that output sets of sites that satisfy them. We also show that, for a particular choice of anisotropic Voronoi diagram, in two dimensions, the well-behaved-ness of the primal anisotropic Voronoi diagram is enough to guarantee that its dual is well-behaved, resulting in an embedded triangulation that is a single-cover of the convex hull of the sites, and has other properties that naturally parallel those of ordinary Delaunay triangulations.
The end-to-end result is a simple and natural condition guaranteeing that
the anisotropic triangulation of a satisfying set of vertices can be constructed
by dualizing their anisotropic Voronoi diagram.
[Joint work with Steven J. Gortler.]
See other events that are part of Brains and Machines Seminar Series 2010/2011
See other events happening in March 2011
