Please note that this seminar has been rescheduled. It will be held on Jan. the 20th CGGC seminar (talk #197) ============ Date: Sunday 20/01/2013 (a week later than previously announced). Time: 13:00 Room: Taub 337 Speaker: Renjie Chen (Computer Science, Technion) Title: Localizing the Delaunay Triangulation and its Parallel Implementation Abstract: The Delaunay triangulation and its dual, the Voronoi diagram, are among the most fundamental structures in computational geometry. We show how to localize the Delaunay triangulation of a given planar point set, namely, bound the set of points which are possible Delaunay neighbors of a given point. We then exploit this observation in an algorithm for constructing the Delaunay triangulation (and its dual Voronoi diagram) by computing the Delaunay neighbors (and Voronoi cell) of each point independently. While this does not lead to the fastest serial algorithm possible for Delaunay triangulation, it does lead to an efficient parallelization strategy which achieves almost perfect speedups on multicore machines. ------------------------------------------------------------------------ Visit the CGGC's web page at <http://www.cs.technion.ac.il/~cggc/> Seminar program: <http://www.cs.technion.ac.il/~cggc/Seminar/Seminar.html> --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: <sigal@cs.technion.ac.il> <sigal@CS.TECHNION.AC.IL>