報(bào)告時(shí)間：2025年3月14日 星期五 下午15:00—17:00
報(bào)告地點(diǎn)：揚(yáng)帆樓304
報(bào)告摘要：
The 2-center problem for a set S of n points in the plane asks for two congruent circular disks of the minimum radius r*, whose union covers all points of S. In this paper, we present an O(n log n) time and O(n) space algorithm for computing r*. Since the lower time bound on the planar 2-center problem is Ω(n log n), both time and space complexities of our algorithm are optimal. Our result improves upon the previously known O(n log 2 n) time algorithm, and solves a long-standing (near thirty years) open problem in computational geometry. It also contains O(n log n) time and O(n) space algorithms for two other variants of the planar 2-center problem: The first is to cover a set of points in convex position, and the second is to cover a convex polygon P, whose goal is to find two centers inside P such that the maximum distance from any point of polygon P to its closest center is minimized.
Except for efficiency of our algorithms, the other novelty is their simplicity: Our algorithms are built on the standard ones for computing the Delaunay triangulation and furthest-site Voronoi diagram of a point set, which are easy to implement. In comparison to most existing 2-center algorithms, no parametric searches are needed.
報(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多篇,。
誠(chéng)邀感興趣的師生參加！
信息科學(xué)技術(shù)學(xué)院
2025年3月6日
最新動(dòng)態(tài)
English
