太阳集团城网站2017(中国)有限公司
当前位置: 首页 > 学术报告 > 正文

On the stretch factor of the Delaunay triangulation (关于德劳内三角剖分的拉伸系数)

发布时间:2024-03-19 09:45:01 发布人:唐振东  

报告题目:On the stretch factor of the Delaunay triangulation(关于德劳内三角剖分的拉伸系数)

报告时间:2024年3月22日 星期五 下午18:00—19:30

会议地点:德济楼102

报告摘要

Let S be a set of points in the plane, and let DT(S) be the planar graph of the Delaunay triangulation of S. For two points a and b of S, denote by |a b| the Euclidean distance between them. Denote by DT(a, b) the shortest path in DT(S) between a and b, and let |DT(a, b)| be the total length of DT(a, b). Dobkin et al. were the first to show that the factor |DT(a, b)|/ |a b| is bounded above by 5.08. Later, this stretch factor was improved to 1.998 by Xia. Very recently, Tan et al. have shown that it can further be reduced to 1.77, for a set of points in convex position. On the other hand, Bose et al. gave a lower bound 1.5846 on the stretch factor of DT(S).

This talk gives a survey on the stretch factor of the Delaunay triangulation, by emphasizing on the constructive methods used in establishing an upper bound. Further direction on this problem is discussed, and several open problems are also posed.

报告人简介

谭学厚现任日本东海大学情报理工学院计算机应用系教授,太阳集团城网站2017讲座教授,并曾于1985年至1987年任教于南京大学计算机科学系。谭学厚1982年毕业于南京大学计算机科学系,1985年获南京大学计算机科学系硕士学位,1991年获日本名古屋大学工学部情报工学科博士学位。1992年至1993年在加拿大Montreal大学和McGill大学博士后工作站工作。谭学厚教授的主要研究方向是计算几何,算法分析与设计,图论和组合优化。主持并完成日本学术振兴会科研项目6项,在Theoretical Computer Science,Algorithmica, Computational Geometry: Theory and Applications,Discrete Applied Mathematics, Journal of Combinatorial Optimization等理论计算机领域知名期刊发表SCI学术论文60多篇。

欢迎全校感兴趣的师生参与!

信息科学技术学院

2024年3月18日