度量空间的概率近似算法

Probabilistic approximation algorithm of metric spaces

通过改进FRT算法,得到随机最小序分割算法(random minimum order partition,RMOP)。在度量空间G中,对点列V进行随机排序(设序列为π),随机选取点u∈V后,获得下标J r(u)=inf{j∈N:d(πj,u)≤r,πj,u∈V},再以点πJr(u)为球心r为半径,对度量空间G进行递归分割,进而形成一棵分层良分割树(hierarchically well separated tree,HST);同时得到E(d T(u,v))≤O(log n)d(u,v)。在RMOP算法与FRT算法具有相同的π时,RMOP算法能保证点u落入特定分割子集B(πJr(u),r)的概率最大。

A new algorithm RMOP was obtained which is called random minimum order partition by improving FRT algorithm. In view of choosing a random permutation 7r for all points of the given metric space G, randomly selecting point u ∈ V, then the order Jr（u）=inf{j∈N：d（πj,u）≤r,πj,u∈V} was derived. Therefore, a hierarchically well separated tree （short for HST） was constructed by recursively partitioning G via some clusters B（πJr（u）,r）, which πJr（u）is the center and r is the radius of the cluster. Moreover, the expectation expression E（dT（u,v））≤0（logn）d（u,v） holds. When FRT algorithm and RMOP algorithm have the same random permutation π, the probabil- ity which ensures the point u lies in the region B（πJr（u）,r） is maximum in the RMOP algorithm.