Computational Information Geometry Wonderland

Olivier recently attended ISVD where he presented the paper
Jensen-Bregman Voronoi diagrams and centroidal tessellations
on my behalf (I had unfortunately teaching duties colliding with the event).
Here is a short trip report

ISVD 2010 -- International Symposium on Voronoi Diagrams in Science and Engineering 

The 7th ISVD International Symposium on Voronoi Diagrams in Science and
Engineering hold in Quebec City, Qc, Canada from the 28th to the
30th of June 2010.
This symposium is devoted to a data structure which is famous in
computational geometry: the Voronoi diagrams. It allows to present both
theoretical results on this field and related ones (power diagrams,
Delaunay triangulations, two-sites diagrams, etc) or applications in
science or engineering (art, data visualization, etc).
The first keynote was made by Prof. Nikolai N. Medvedev from Novosibirsk
State University, Russia: he made a very interesting talk about the
impact of Delaunay on Voronoi diagrams, completed by a biography of
Boris Delaunay killing some myths about his life. The second one was
made by Sergio de Biasi, courageously replacing the planned speaker,
describing polynomiography and showing a lot of great images. The third
invited speaker, Prof. Leonidas J. Guibas from Stanford University,
first described a method for recovering curvature from a sampled 3D
shape, with theoretical guaranties, and next a Voronoi diagram
application to routing in sensors network. The last speakers, Prof.
Menelaos Karavela from the University of Crete, presented the CGAL
library, from theory to practice.
Some words about a few talks I particularly enjoyed: Toshihiro Tanuma
presented the paper /Revisiting Hyperbolic Voronoi Diagrams from
Theoretical, Applied and Generalized Viewpoints/, showing a new proof
that hyperbolic diagrams are power diagrams with some applications to
graphs embedding. Sergio De Biasi spoke about the paper /Maximal Zone
Diagrams and Their Computation/, describing a variation on zone diagrams
and some interesting properties about it. Danyel Fisher, presenting
/Fast Dynamic Voronoi Tree maps/, described new visualization techniques
with applications ranging from disk space visualization to display of
bug reports.
The conference was very well organized: except for the very last
session, which was made using Skype and thus a bit difficult to follow,
everything everything went without any particular problem.

Olivier & Frank.

On sunday is the 2010 Int. Symp. on Voronoi Diagrams (ISVD). We shall present: Jensen-Bregman Voronoi diagrams and centroidal tessellations

Here are the slides of the talk.
The Jensen-Bregman divergence is a distortion measure defined by the Jensen difference provided by a strictly convex function. Jensen-Bregman divergences extend the well-known Jensen-Shannon divergence by allowing to choose an arbitrary convex function generator instead of the standard Shannon entropy. This class of Jensen-Bregman divergences notably includes the squared Euclidean distance. Although Jensen-Bregman divergences are symmetric distances by construction, they are not metrics as they violate the triangle inequality. We study the geometric properties and combinatorial complexities of both the Voronoi diagrams and the centroidal Voronoi diagrams induced by such as class of information-theoretic divergences. We show that those Jensen- Bregman divergences appear naturally into two contexts: (1) when symmetrizing Bregman divergences, and (2) when computing the Bhattacharyya distances of statistical distributions. The Bhattacharyya distance measures the amount of overlap of distributions, and is popularly used to provide both lower and upper bounds in machine learning: the Bayes? misclassification error. Since the Bhattacharyya distance of popular distributions in statistics called the exponential families (including familiar Gaussian, Poisson, multinomial, Beta/Gamma families, etc.) can be computed equivalently as Jensen-Bregman divergences, the Jensen-Bregman Voronoi diagrams allow one also to study statistical Voronoi diagrams induced by an entropic function. Keywords-Jensen?s inequality, Jensen difference, Bregman divergences, Jensen-Shannon divergence, Bhattacharyya distance, Burbea-Rao divergence, Hellinger-Kakutani-Matusita divergences, f-divergence, -divergence, exponential families, information geometry.

The Jensen-Bregman divergence is a distortion measure defined by the Jensen difference provided by a strictly convex function. Jensen-Bregman divergences extend the well-known Jensen-Shannon divergence by allowing to choose an arbitrary convex function generator instead of the standard Shannon entropy. This class of Jensen-Bregman divergences notably includes the squared Euclidean distance. Although Jensen-Bregman divergences are symmetric distances by construction, they are not metrics as they violate the triangle inequality. We study the geometric properties and combinatorial complexities of both the Voronoi diagrams and the centroidal Voronoi diagrams induced by such as class of information-theoretic divergences. We show that those Jensen- Bregman divergences appear naturally into two contexts: (1) when symmetrizing Bregman divergences, and (2) when computing the Bhattacharyya distances of statistical distributions. The Bhattacharyya distance measures the amount of overlap of distributions, and is popularly used to provide both lower and upper bounds in machine learning: the Bayes? misclassification error. Since the Bhattacharyya distance of popular distributions in statistics called the exponential families (including familiar Gaussian, Poisson, multinomial, Beta/Gamma families, etc.) can be computed equivalently as Jensen-Bregman divergences, the Jensen-Bregman Voronoi diagrams allow one also to study statistical Voronoi diagrams induced by an entropic function.

One cool application of centroidal Voronoi tesselations is stippling. Stippling is an artistic rendering of images using the grey intensities as the underlying point density for uniform sampling. Here is a (preliminary) result (of myself):

Geometries are abstract by essence but we visualize them using embedding into the good old Euclidean 2D/3D spaces: our sheet of paper, or 3D browser. So consider hyperbolic geometry, it has many different realizations: conformal or not. In a conformal representation such as Poincare upper-space or ball, angles are preserved. That is, angles measured in the Euclidean geometry coincide with angles in the hyperbolic geometry. Conformal representations are therefore often wished for mapping because it tends to minimize distortions locally.

The Voronoi diagram on hyperbolic geometry has thus been studied in conformal Poincare upper-plane representation. However, geodesics are visualized by arcs of circles and it makes computation more difficult if not tricky. Another problem is that it requires more numerical precision to carry out predicate evaluations.

Now consider the Klein ball realization. In this non-conformal representation, geodesics are straight line segment (but the mid Euclidean point is not the mid hyperbolic point). Bisectors are also hyperplanes and the diagram is therefore affine, and can be computed from an equivalent power diagram. So hyperbolic Voronoi diagrams are handy and do not require more specific implementation than a weighted Voronoi diagram.

The details are explained in the following report, illustrated with an application on image browsing
PDF

Using s/w volume rendering,we can easily visualize Voronoi structures in 3D. The picture below is a screen capture of an interactive s/w using GPU shaders. We can similarly visualize the quantum voronoi diagrams inside the Bloch ball...
VorL2.bmp