“离散几何前沿”系列报告
主讲人
谭学厚 教授（日本东海大学）
主讲人简介
谭学厚，现任日本东海大学情报理工学院计算机应用系教授，大连海事大学讲座教授，并曾于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多篇。
报告一
主题
New progress on the stretch factor of the Delaunay triangulation
时间
2025年9月11日（周四）14:00-16:00
地点
广东外语外贸大学（大学城校区）院系楼152室
内容简介
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.73, 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.
报告二
主题
A new approach to the two-center problem for pairs of points
时间
2025年9月14日（周日）14:40-16:40
地点
广东外语外贸大学（白云山校区）一教南117室
内容简介
In this talk, we introduce the following MinMax two-center problem for pairs of points: Given a set S of pairs of points in the plane, we want to find the two disks having the minimum radius of larger disk such that two points of every pair in S have one in a disk and the other in another; both points of a pair are allowed to be contained in a same disk. This problem, which was by introduced by Arkin et al., is also termed the bichromatic MinMax two-center problem, in which one wants to color one point of each pair red and the other blue, in such a way that the larger radius between two smallest disks enclosing n red and n blue points respectively is minimized. We present a new, simple approach to the MinMax 2-center problem for pairs of points.
报告三
主题
An optimal and practical algorithm for the planar 2-center problem
时间
2025年9月18日（周四）14:00-16:00
地点
广东外语外贸大学（大学城校区）院系楼152室
内容简介
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.
