演講公告

演講主題：Partition points in the plane to minimize the sum of perimeters, diameters and radii
主講人：黃光明教授 (Prof. Frank K. Hwang)
演講日期：2008年1月17日(星期四)<br>下午2:00-3:00
演講地點：(光復校區)科學一館223室
摘要內容：
In 1991, Capoyleas, Rote and Woeginger published a paper in the prestigious Journal of Algorithms proving that there exists a separable partition of n points in the plane into p parts such that the sum of parameters (or diameters or radii) over these parts are minimized among all partitions. Here "separable" means that the convex hulls of these p parts are disjoint. This paper is full of ingenious ideas, fitting the fame of the authors and the reputation of the journal. But we will show that even in such a paper, a careful reading can still find some serious incompleteness in proofs (for perimeters and diameters) and a nontrivial extension of the radii result. All it takes is some basic knowledge in plane geometry, which we all have acquired in high school. So it pays to read a paper in depth with a critical eye.

$返回$ go back