論文編號:SXJY167  論文字數:4384,頁數:05

平面上給定點集最小覆蓋問題的快速近似新算法及應用
 摘要：本文研究了平面中給定點集最小覆蓋圓的問題，討論了求解最小覆蓋圓的近似算法，并得到了一種新的算法。文中提出了新的坐標系，并在此新的坐標系中進一步研究快速近似算法，得出新算法的時間復雜度為0（n）。
 關鍵字：最小覆蓋；時間復雜度；坐標系；GIS；
 1、引言：
 求一個最小圓包含給定點集所有點的問題是人們在實踐和理論上都十分感興趣的問題。由于這個圓的圓心是到點集最遠點最近的一個點，因而在規劃某些設施時很有實用價值。這個圓心也可看成是點集的中心。在圖形學中，圓也常可取作邊界盒，使用它可減少很多不必要的計算。在空間數據庫中可將該問題用于建立空間數據的索引以提高查詢速度。這個問題看起來十分簡單，但用直觀的算法去解此問題，其復雜性可達0（n4），其中n為點集中點的數目［1］。
國際上對于點集的最小覆蓋問題有一種統一的算法就是卡馬克算法，基于它的思路在平面中已經很好地研究了點集的最小覆蓋問題，還解決了平面中給定點集的最小覆蓋快速近似算法問題。該問題在雷達布局、導彈布置、衛星通信、交通規劃、無線電臺廣播、日常生活和經濟等領域的應用進行了廣泛的研究和探討，并得到了很多成果。