報告時間：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.
報告人簡介：
譚學厚現任日本東海大學情報理工學院計算機應用系教授，大連海事大學講座教授，并曾于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多篇。
誠邀感興趣的師生參加！
信息科學技術學院
2025年3月6日
English
最新動態