复旦大学大三学子一朝11年曼哈顿难题

　　“利用给定平面上的一个点集，构造总长度最小的网络，使得任意两点之间都有长度最短的路径相连”―――这一根据曼哈顿城市地图抽象而出的“最小曼哈顿”难题，已在全球数学界求解11年。日前，复旦大学大三本科生郭泽宇和25岁的博士研究生孙贺成功解题，受到全球学界瞩目。

　　“曼哈顿难题”不仅是一个数学领域的技术“难关”，其应用价值同样巨大，无论对城市规划、网络路由、大规模集成电路设计还是在计算生物学等众多前沿领域，都有着重要意义。在日前举行的第25届计算几何国际大会上，两位中国年轻人受邀讲解其最小曼哈顿网络问题算法和复杂性的研究。郭泽宇仅用20分钟就展现了证明轮廓，不少与会代表为其论文中所展现出的对问题罕见的洞察力、复杂巧妙的证明而惊叹。

　　自2007年起，郭泽宇和孙贺就开始致力于最小曼哈顿网络问题算法和复杂性的研究。去年6月，郭泽宇受到复旦大学本科生学术研究资助计划“q政学者”项目的资助，在孙贺的指导下开展学术研究。到2008年，他们先后给出了目前为止最简单的算法。2008年11月末，他们将论文投稿到第25届计算几何国际大会中。今年2月13日清晨，大会程序委员会传来喜讯：他们的论文在近170篇文章中脱颖而出，并作为最佳论文之一受邀向世界顶级期刊《离散与计算几何》投稿。