度量空间的概率近似算法

作者：蔡裕华 魏凤英hsts树度量随机分割概率近似算法

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

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社