搜索
报告题目：New algorithms for touring a sequence of convex objects（有序凸体的遍历算法研究）
报 告 人：谭学厚 日本东海大学
报告摘要：Given a set of cites along with the cost of travel between each pair of them, the traveling salesman problem, or TSP for short, is to find the cheapest way of visiting all the cites and returning to the starting point. It is well known that the TSP is NP-hard. However, if some order or a partial order of the cities to visit is given, polynomial-time solutions exist in most cases. This talk gives a survey of recent work on the problems of touring a sequence of line segments, convex polygons in the plane and inside a polygonal region. The well-known watchman route problem, which asks for a shortest route along which a mobile robot can see a given polygon, can be also interpreted as a problem of touring a sequence of chords inside a polygon. Algorithmic techniques developed for the touring objects problems, including a data structure, called the last step shortest path maps, are investigated. An interesting result is that the traveling salesman problem for lines and rays in the plane can be solved in O(n4) and O(n5) time, respectively.
报告人简介：谭学厚现任日本东海大学情报理工学院计算机应用系教授，大连海事大学讲座教授，并曾于1985年至1987年任教于南京大学计算机科学系。谭学厚1982年毕业于南京大学计算机科学系，1985年获南京大学计算机科学系硕士学位，1991年获日本名古屋大学工学部情报工学科博士学位。1992年至1993年在加拿大Montreal大学和McGill大学博士后工作站工作。谭学厚教授的主要研究方向是计算几何，算法分析与设计，图论和组合优化。主持日本学术振兴会项目6项，在Theoretical Computer Science，Algorithmica, Computational Geometry: Theory and Applications，Discrete Applied Mathematics等理论计算机领域知名期刊发表学术论文100余篇。
报告时间：2026年3月13日 14:00-15:00
报告地点：文渊楼 B119
主办单位：数学与统计学院
学院宣传片
