小覆平面上給定點(diǎn)集最蓋問(wèn)題的快速近似新算法及應(yīng)用

論文編號(hào):SXJY167  論文字?jǐn)?shù):4384,頁(yè)數(shù):05

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