基于GEOFILTERKRUSKAL算法的几何最小生成树

### 基于GEOFILTERKRUSKAL算法的几何最小生成树 #### 1. 引言 在计算几何领域，寻找一组点的最小生成树（MST）是一个经典问题。本文将介绍一种名为GEOFILTERKRUSKAL的算法，它用于计算几何最小生成树（GMST），并对其正确性、运行时间进行分析，还给出了实验结果。 #### 2. 相关算法基础 - **Bccp算法** - Bccp算法用于计算两个集合之间的最近点对及其距离。以下是Bccp算法的代码： ```plaintext Algorithm 1. Bccp Algorithm [31]: Compute {p′, q′, δ′} =BCCP(a, b[, {p, q, δ} = η]) Require: a, b ∈Q, A, B ⊆P, δ ∈R+ Require: If {p, q, δ} is not specified, {p, q, δ} = η, an upper bound on Bccp(a, b). 1: procedure BCCP(a,b[, {p, q, δ} = η]) 2: if (|A| = 1 and |B| = 1) then 3: Let p′ ∈A, q′ ∈B 4: if Dist(p′, q′) < δ then return {p′, q′, Dist(p′, q′)} 5: else 6: if Vol(a) < Vol(b) then Swap(a,b) 7: γ =MinDist(Left(a),b) 8: ζ =MinDist(Right(a),b) 9: if γ < δ then {p, q, δ} =BCCP(Left(a),b, {p, q, δ}) 10: if ζ < δ then {p, q, δ} =BCCP(Right(a),b, {p, q, δ}) 11: return {p, q, δ} 12: end procedure ``` - 该算法的主要思路是，如果两个集合都只有一个点，则直接计算它们之间的距离；否则，根据集合的体积大小进行交换，并递归计算左右子集合与另一个集合的最小距离。 - **Kruskal算法** - Kruskal算法是一种经典的计算最小生成树的算法。它按边的权重从小到大的顺序考虑边，使用并查集（UnionFind）数据结构来检查边的两个端点是否属于同一个连通分量，如果不属于，则将该边加入最小生成树。 #### 3. GEOFILTERKRUSKAL算法 - **算法描述** - 输入是点集$P \subseteq R^d$的一个良好分离对分解（WSPD）。算法将WSPD集合$S$划分为$E_l$和$E_u$，其中$E_l$包含基数小于阈值$\beta$（初始为2）的WSP，$E_u = S \setminus E_l$。 - 计算$E_l$中所有元素的Bccp，计算$E_u$中所有$(a, b)$的$MinDist(a, b)$的最小值$\rho$。 - 将$E_l$进一步划分为$E_{l1}$和$E_{l2}$，$E_{l1}$包含Bccp距离小于$\rho$的元素，$E_{l2} = E_l \setminus E_{l1}$。 - 将$E_{l1}$传递给KRUSKAL过程，将$E_{l2} \cup E_u$传递给FILTER过程。 - KRUSKAL过程将边加入GMST或丢弃已连接的边，FILTER过程移除所有已连接的WSP。 - 递归调用GEOFILTERKRUSKAL过程，每次将阈值$\beta$增加1，直到构建出最小生成树。 以下是GEOFILTERKRUSKAL算法的代码： ```plaintext Algorithm 2. GEOFILTERKRUSKAL Algorithm Require: S = {(a1, b1), ..., (am, bm)} is a WSPD, constructed from P ⊆Rd ; T = {}. Ensure: Bccp Threshold β ≥2. 1: procedure GEOFILTERKRUSKAL(Sequence of WSPs : S, Sequence of Edges : T, UnionFind : G, Integer : β) 2: El = Eu = El1 = El2 = ∅ 3: for all (ai, bi) ∈S do 4: if (|ai| + |bi|) ≤β then El = El ∪{(ai, bi)} else Eu = Eu ∪{(ai, bi)} 5: end for 6: ρ = min{MinDist{ai, bi} : (ai, bi) ∈Eu, i = 1, 2, ..., m} 7: for all (ai, bi) ∈El do 8: {u, v, δ} = Bccp(ai, bi) 9: if (δ ≤ρ) then El1 = El1 ∪{(u, v)} else El2 = El2 ∪{(u, v)} 10: end for 11: KRUSKAL(El1, T, G) 12: Enew = El2 ∪Eu 13: FILTER(Enew, G) 14: if ( |T| < (n −1)) then GEOFILTERKRUSKAL(Enew, T, G, β + 1) 15: end procedure 16: procedure KRUSKAL(Sequence of WSPs : E, Sequence of ```