2025-04-13
下面问题皆考虑二维情形.
格点离散化
将整个平面划分为 \(l\times l\) 的正方形块，然后将平面上的每个数据点归到最近的格点（正方形中心）.
一个简单的问题：\(1+\epsilon\) 近似直径.
在上面的离散化中，两个点的距离变化不会超过 \(\sqrt{2}l\).
先通过取任一点求最远点找到直径的 \(2-\) 近似 \(T\). 于是 \(1+\epsilon\) 近似只需要取 \(l=T\epsilon/\sqrt{2}\).
这个方法求点集的 \(1+\epsilon\) 近似直径只需要复杂度为 \(O(n+\frac{1}{\epsilon^2})\).
然后看一个最小包围圆的问题.
引入一个 Coreset 的概念：定义点集 \(S\) 的 \(\epsilon-\)coreset 为 \(T\) 使得 \(T\subset S\) 且 \(T\) 的答案为 \(S\) 的 \(\epsilon\) 近似. 可以发现上述取 $l=R'/2 $ 得到的离散化后的点集随便改一改就是一个 coreset. 其中 \(R'\) 为 \(2-\)近似.
Coreset 支持一个分治. 可以先求出 \(S\) 和 \(T\) 的 coreset，然后再这两个 coreset 并起来再求一个 coreset，就得到了 \(S\cup T\) 的 coreset.
四分树
考虑对于原本的平面，横竖各切一半得到四个子平面，然后不断这样递归下去，直到边长为 \(1\) 或里面只有一个点.
那么这棵树至多 \(\log V\) 层，并且节点数是 \(O(n\log V)\). \(d\) 维度的时候可以通过简单的优化使得只需要乘上 \(d\)（空的节点不需要占用空间）.
有一些优化. 比如像压缩 trie 一样可以同样压缩四分树使得节点数线性.
考虑如何用四分树支持动态的最近邻查询.
假如我们查询点 \(x\) 的最近邻. 假如我们到某个阶段的时候，有着当前答案 \(q'\)，在节点 \(u\)，节点 \(u\) 有四个儿子 \(v_k\)，那么我们希望只有在 \(v_k\) 中不存在 \((1+\epsilon)q<q'\) 的 \(q\) 时才不递归进入 \(v_k\). 判断这点的时候考虑使用近似：我们对每个节点随便选择一个代表元 \(y\)，那么将 \(q\) 放缩至 \(dis(x,y_{v_k})-diam(v_k)\)，其中 \(diam(v)\) 可以用 \(v\) 的长度的 \(\sqrt 2\) 倍放缩.
正确性大抵比较清晰. 考虑一下复杂度. 首先如果 \(diam(u)<\epsilon \times ans/2\) 那就肯定不会继续递归下去了. 然后感受一下，一个儿子如果被递归了，那么其 \(x\) 到代表元不会太远（实际上 \(O(\epsilon^{-1}diam)\)），所以所有深度相同的代表元都在一个圆中，而半径为 \(R\) 的圆中的 \(l\) 正方形数量至多有 \((\frac{R}{l})^2\) 个，所以复杂度最后在 \(O(\epsilon^{-2}\log V)\).
WSPD
有 \(n^2\) 个点对，考虑对于点对离散化.
比如有两坨点，每坨点之间间距不大，但是这两坨点间距很大，那么就不用分别记录两坨点中每个两个点的距离.
定义 \(\epsilon-\)WSPD 为一个序列，序列中的每个元素都是两坨点形成的 pair \((A_i,B_i)\)，其中 \(\max (diam(A_i),diam(B_i))<\epsilon dis(A_i,B_i)\). 并且 \(\cup_i A_i\times B_i=P^2\).
WSPD 可以用四分树高效表示. 具体而言，令 \(work(u,v)\) 表示处理节点 \(u\) 和节点 \(v\) 形成的 pair 的 WSPD，那么不妨设 \(diam(u)>diam(v)\). 那么就如果 \((u,v)\) 是合法 pair 直接返回，否则递归所有 \((u_i,v)\). \(u_i\) 为 \(u\) 的儿子.
这个算法构造的 \(\epsilon-\)WSPD的项数是 \(O(n\epsilon^{-O(d)}\log V)\) 的.
一个应用：精确求解最近点对. 因为如果最近点对 \(p,q\) 满足 \(p\in A_i\) 而 \(q\in B_i\) 那么肯定 \(|A_i|=|B_i|=1\).
另一个应用是近似直径：取 \(\epsilon/2-\)WSPD，然后求 \(A_i,B_i\) 的代表元距离.
欧式图的 \(t-\)Spanner：对欧几里得平面的完全图，找一个子图，使得 \(dis(x,y)\le t||x-y||\). 取 \(\epsilon/8-\)WSPD，代表元连边然后每个点再连代表元即可.
运用 \(t-\)Spanner 就可以做欧式平面的最小生成树的近似. 但是你要取 \(\epsilon/8\) 的话很有可能常数就超过了你的 \(n\). 而实际上，取 \(t\) 较大（甚至 \(=1\)）就已经能2 有很好的结果.