報告時間：2025年3月14日 星期五 下午15:00—17:00
報告地點：揚帆樓304
報告摘要：
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.
報告人簡介：
譚學(xué)厚現(xiàn)任日本東海大學(xué)情報理工學(xué)院計算機應(yīng)用系教授，大連海事大學(xué)講座教授，并曾于1985年至1987年任教于南京大學(xué)計算機科學(xué)系。譚學(xué)厚1982年畢業(yè)于南京大學(xué)計算機科學(xué)系，1985年獲南京大學(xué)計算機科學(xué)系碩士學(xué)位，1991年獲日本名古屋大學(xué)工學(xué)部情報工學(xué)科博士學(xué)位。1992年至1993年在加拿大Montreal大學(xué)和McGill大學(xué)博士后工作站工作。譚學(xué)厚教授的主要研究方向是計算幾何，算法分析與設(shè)計，圖論和組合優(yōu)化。主持并完成日本學(xué)術(shù)振興會科研項目6項，在Theoretical Computer Science，Algorithmica, Computational Geometry: Theory and Applications，Discrete Applied Mathematics, Journal of Combinatorial Optimization等理論計算機領(lǐng)域知名期刊發(fā)表SCI學(xué)術(shù)論文60多篇。
誠邀感興趣的師生參加！
信息科學(xué)技術(shù)學(xué)院
2025年3月6日
English
最新動態(tài)