Technion
 
CGGC seminar (talk #197)
 
============

 THIS TALK WILL BE GIVEN ON 20/1/13, A WEEK LATER THAN ORIGINALLY ANNOUNCED. 
SEE A SEPARATE ANNOUNCEMENT FOR DETAILS OF THE TIME AND PLACE.


 
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>