標題: 以最遠弗洛若依圖方法求一組圓的最小包封圓
作者: 陳東元
CHENG, DONG-YUAN
杜敏文
DU, MIN-WEN
電控工程研究所
關鍵字: 最遠弗洛依圖;組圓;最小包封圓;圓;凸形覆被
公開日期: 1985
摘要: 在本論文中,我們將討論平面上組圓的幾個計算幾何問題。所討論的問題包括凸形覆 被問題、遠弗洛若依圖問題及最小包封圓問題。我們將提出數個解決上述問題的計算 法則。 對於N 個圓凸形覆被問題,我們提出二種法--禮物包紮法及分擊法。其時間複雜度 分別為(hH)及O(NlogN),其中h 為凸形覆被邊緣直線段的數目。對於N 個圓的最小包 封圓問題,我們採用最遠弗洛若依圖方法來解決。我們將討論一組圓其最遠弗洛若依 圖的定義、性質,並提出一間複雜度為O(N□) 的方法來產生一組圓的最遠弗洛若依 圖。最後利用最遠弗洛若依圖,我們可以到O(N□) 的方法來求N個圓的最小包封圓。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT742146014
http://hdl.handle.net/11536/52343
顯示於類別:畢業論文