報告題目：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.

報告人簡介：

譚學厚現任日本東海大學情報理工學院計算機應用系教授，大連海事大學講座教授，并曾于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日