CGGC seminar (talk #191)
Date: Sunday 03/06/2012
Time: 13:00
Room: Taub 337
Speaker: Daniel Reem (IMPA, Rio, Brasil)
Title: On the possibility of simple parallel computing of Voronoi diagrams
and Delaunay graphs
Although many algorithms for computing Euclidean Voronoi diagrams of point
sites have been published, most of them are sequential in nature and hence
cast inherent difficulties on the possibility to compute the diagrams in
parallel. We present a new algorithm which enables the (combinatorial)
computation of each of the Voronoi cells independently of the other ones.
The algorithm is significantly different from previous ones and some of
the ideas related to it are in the spirit of convex analysis.
A new combinatorial structure for representing the cells is described
along the way, and the computation of the corresponding Delaunay graph
follows as a simple consequence.
An implementation of the algorithm (done by Omri Azencot) will be
 Visit the CGGC's web page at  <>
 Seminar program:  <>
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from:  <>   <sigal@CS.TECHNION.AC.IL>