報(bào)告題目：On the stretch factor of the Delaunay triangulation（關(guān)于德勞內(nèi)三角剖分的拉伸系數(shù)）

報(bào)告時(shí)間：2024年3月22日 星期五 下午18:00—19:30

會(huì)議地點(diǎn)：德濟(jì)樓102

報(bào)告摘要：

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.

報(bào)告人簡(jiǎn)介：

譚學(xué)厚現(xiàn)任日本東海大學(xué)情報(bào)理工學(xué)院計(jì)算機(jī)應(yīng)用系教授，大連海事大學(xué)講座教授，并曾于1985年至1987年任教于南京大學(xué)計(jì)算機(jī)科學(xué)系,。譚學(xué)厚1982年畢業(yè)于南京大學(xué)計(jì)算機(jī)科學(xué)系，1985年獲南京大學(xué)計(jì)算機(jī)科學(xué)系碩士學(xué)位,，1991年獲日本名古屋大學(xué)工學(xué)部情報(bào)工學(xué)科博士學(xué)位。1992年至1993年在加拿大Montreal大學(xué)和McGill大學(xué)博士后工作站工作。譚學(xué)厚教授的主要研究方向是計(jì)算幾何,，算法分析與設(shè)計(jì),，圖論和組合優(yōu)化。主持并完成日本學(xué)術(shù)振興會(huì)科研項(xiàng)目6項(xiàng),，在Theoretical Computer Science,，Algorithmica, Computational Geometry: Theory and Applications，Discrete Applied Mathematics, Journal of Combinatorial Optimization等理論計(jì)算機(jī)領(lǐng)域知名期刊發(fā)表SCI學(xué)術(shù)論文60多篇,。

歡迎全校感興趣的師生參與,！

信息科學(xué)技術(shù)學(xué)院

2024年3月18日