高維空間近似最小球覆蓋問題的研究.pdf

1、本文主要討論高維空間球集最小球覆蓋問題和二維空間圓集最小圓覆蓋問題。
　　 高維空間最小球覆蓋問題是指對于給定的高維空間球集S，求解覆蓋S中所有球的最小球。
　　 二維空間最小圓覆蓋問題是高維空間最小球覆蓋問題的特例（維數(shù)d=2）。
　　 點集和圓集的覆蓋問題目前已經有很多求解算法。由于這些算法對內存的過度需求，導致我們無法在合理的時間內求解大數(shù)據量問題。Badoiu提出了核心集的概念，降低了求解該問題的復雜性。

2、本文通過引入核心集的思想，改進了球集和圓集覆蓋問題的各種算法。
　　 提出了球集直徑的概念，給出了求解球集直徑的近似算法，并證明了該算法至少可以得到1/3倍球集直徑近似值。
　　 給出了求解高維空間球集最小球覆蓋問題的1+ε近似算法。其中核心集的大小為0（1/ε），算法的時間復雜度為O（nd/ε+(d2/ε3/2)(1/ε+d)log(1/ε)）。
　　 通過引入核心集的思想，改進了二維空間圓集最小圓覆蓋問題的各