以最遠弗洛若依圖方法求一組圓的最小包封圓

Abstract

在本論文中，我們將討論平面上組圓的幾個計算幾何問題。所討論的問題包括凸形覆 被問題、遠弗洛若依圖問題及最小包封圓問題。我們將提出數個解決上述問題的計算 法則。 對於N 個圓凸形覆被問題，我們提出二種法－－禮物包紮法及分擊法。其時間複雜度 分別為(hH)及O(NlogN)，其中h 為凸形覆被邊緣直線段的數目。對於N 個圓的最小包 封圓問題，我們採用最遠弗洛若依圖方法來解決。我們將討論一組圓其最遠弗洛若依 圖的定義、性質，並提出一間複雜度為O(N□) 的方法來產生一組圓的最遠弗洛若依 圖。最後利用最遠弗洛若依圖，我們可以到O(N□) 的方法來求N個圓的最小包封圓。