报告时间：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 ² 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.

报告人简介：

谭学厚现任日本东海大学情报理工学院计算机应用系教授，MK体育(中国)国际平台讲座教授，并曾于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日