research
这是 从带权图到流形测地线 的第 5 篇。
Dijkstra 是 \(O(|E|+|V|\log|V|)\),精确。流形测地线在一般度量下要解 eikonal,数值上就是网格上的 Fast Marching,更慢,还有离散化误差。
Y 形实验里,\(120^\circ\) 的射线不贴网格时,Fast Marching 会把长度抬到 2 以上。连续上这不可能,因为图上折线已经是长为 2 的可容许曲线。网格把便宜走廊切碎了。
所以这个构造不能当作更快的最短路算法。用处在别处:给带权图一个光滑的变分结构,能谈测地流、曲率和热核,并能控制它们和图距离的差距;把路上的离散对象写成同一个能量的临界点;作为离散到连续的局部模型,顶点处是各向异性,边上是一维区间。
若某张图能低畸变地嵌进球面或双曲空间,闭式测地线可以当近似。那过不了第 1 篇的等距障碍,只能近似。
已经有的,和还空着的
度量图、quantum graph、细管流形的谱收敛、ribbon graph、各向异性 Fast Marching、图等距嵌入黎曼流形的分类,这些都有。还空着、而且和这个想法对齐的,是从边权显式造出 \(g\),并给出 \(d_g\) 与 \(d_G\) 的定量误差;测地线与最短路的边集一致;分支点处各向异性的局部模型。
深度是一篇短笔记的核心引理,不是一个新领域。值得写,是因为命题干净,Y 形可以先算后证。
三维里用柄把图加厚,通常会在柄上造出捷径。那一条单独写在 图的三维增厚。合订本是 highway-metric.pdf。