research
这是 从带权图到流形测地线 的第 2 篇。上一篇说明精确等距做不到。
不把图本身做成流形。先把 \((G,w)\) 做成度量图 \(\Gamma\),嵌进平面或一条 ribbon 曲面,再在周围放一个光滑的共形因子:沿边走便宜,离开边昂贵。
\[ g_x=\rho(x)^2\,dx^2,\qquad \rho(x)=\rho_{\mathrm{on}}+\lambda\,\varphi\bigl(d(x,\Gamma)/\delta\bigr). \]
\(\varphi(0)=0\),\(\varphi(t)=1\)(\(t\ge 1\)),中间用平滑阶梯。边上把 \(\rho_{\mathrm{on}}\) 调成沿边积分等于 \(w_e\),图上的折线长度仍是 \(d_G\)。因此对任意 \(\lambda,\delta\),
\[ d_g\le d_G. \]
测地线只会更短,不会更长。短多少,就是抹角误差。
这和路网、各向异性 Fast Marching 是同一类度量。这里要问的不是怎么数值求测地线,而是:边权给定之后,这个度量的测地距离在多大程度上等于图距离。
五层
整件事是五个映射接起来,每一层只做一件事。
1. 组合数据:图、边权、顶点处的循环序。 2. 几何实现:ribbon 曲面、上面的度量图、顶点的位置。 3. 标记:长度写入 \(\rho\),边的身份写入另一张表 \(\sigma\)。 4. 变分:测地距离 \(d_g\) 和实现它的曲线 \(\gamma\)。 5. 查表:把 \(\sigma(\gamma(t))\) 读回一条顶点序列。
Y 形上,误差是 \(\delta\,\lambda^{-1/p}\) 这一级。一般图上,边上不能省路,测地线只在顶点处抹角,于是有组合型的管子定理。边权不是只写一个正实数:长度进 \(\rho\),身份进钥匙再插值成 \(\sigma\)。
下一篇在最简单的分支上把误差算出来:Y 形。