雙直徑問題的近似計算方法

Abstract

Ｐ是平面上含ｎ點的集合，雙直徑問題是將點集Ｐ分割成Ｓ、Ｔ兩子集，使得這兩子 集直徑的較大者愈小愈好。雙直徑問題已經有ｏ（n□log n）的方法〔Avis８６〕。 在這篇論文中，我們提出一個ｏ（n□log n） 的近似計算方法，此方法滿足ε—sub optimal的要求。