国家数学与交叉科学中心合肥分中心报告会

报告题目：Exploiting locality in geometry and parallel algorithms

报 告 人：Dr. Renjie Chen, Technion, Israel       

报告时间：2013年3月5日 星期二 上午10:00-11:30

报告地点：管理科研楼1208室

Abstract：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.
As an application of the Delaunay triangulation, we describe a fast sampling algorithm for generating uniformly-distributed point patterns with good blue noise characteristics. We first show a local characterization for the state-of-the-art blue noise distribution, i.e. farthest point distribution (FPD).
Then, we introduce the constrained farthest point optimization algorithm, which is provably optimal and may be easily parallelized, resulting in an algorithm whose performance/quality trade-off is superior to other state-of-the-art approaches.

Short bio:
Renjie Chen received his BSc degree in Applied Mathematics from Zhejiang University in Jun. 2005 and PhD degree in Applied Mathematics from Zhejiang University in Jul. 2010. From Aug. 2010 to Mar. 2011, he was a research assistant in Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences. Since Apr. 2011, he is a postdoctoral fellow in the Technion - Israel Institute of Technology. His
research interests include computer graphics, digital image/geometry processing, geometric modeling, discrete differential geometry and computational geometry.

主办单位：中国科学技术大学数学科学学院

          国家数学与交叉科学中心合肥分中心

欢迎感兴趣的师生参加！