ACM通信
研究突出了
技术视角:用测地线方法探索一个王国
从前，有一个特别慷慨的国王。他决定把他的土地分给他所有的人民。任何有房子的家庭都必须用一块石头在他们土地的中心做标记。然后判决说，他们能到达的距离标记石1000步以内的每一个点都属于他们。
起初，国王因其统治的简单明了而受到称赞。然而，当大多数新的土地所有者决定在他们的财产周围建立一个栅栏时，他们很快意识到确定栅栏的位置是令人沮丧的困难。走了1000步之后到达的任何一个点都是财产的一部分，当然;但是一个人要怎么走才能到达离石头尽可能远的地方呢?
比较幸运的土地所有者居住在地势平坦的地区，沿着直线走(例如，走到距离1,000步以上的任何地标)总会到达土地边界上的一个点。山区的土地所有者有一个问题。他们需要找到一条相当于直线的路径。这样的路径现在被称为测地线，这个名字确实与问题有关测量的地球。用今天的语言来说，分配给每个家庭的土地是一个测地圆盘。弯曲区域内两点之间的距离是科学和工程中众多应用的一个基本问题，这一点不足为奇。
那么，我们如何在数字计算机上解决计算测地线路径、距离和圆的问题呢?让我们假设光滑的地形是近似的三角剖分。从这个三角网的一个顶点到所有其他顶点的最短路径沿着边缘的三角剖分可以用Dijkstra算法计算。虽然这为寻找路径的问题提供了一个有效的解决方案，但只沿着三角形的边缘移动不会得到最短的可能路径。一个更好的选择是跟踪波前是如何从源顶点发出的，所谓的快速行进法。
不幸的是，这种方法可能无法为某些曲面和三角形形状提供最短路径。事实证明，分段线性曲面上的最短路径问题具有超二次最差情况复杂度，而建立这种复杂度的算法出奇地复杂。这类最新的算法在通常的实际情况下具有更好的渐近复杂度，但它们仍然明显比简单的图遍历(如Dijkstra的图遍历)复杂。
Crane、Weischedel和Wardetzky在接下来的论文中提出的方法可能与土地所有者可以观察和利用的东西有关:假设一个人从标记石开始，随机走1000步，并用一块鹅卵石标记这条路的终点。经过多次重复这种练习，地面上的鹅卵石分布就出现了:越靠近标记石头，图案越密集，越远的地方发现的鹅卵石就越少。事实证明，从标记石头开始，一直朝石头较少的方向走，就会得到想要的测地线路径。或者，用最近的说法，随机游走的概率密度函数的梯度与测地线平行。
我们如何在数字计算机上解决计算测地线路径、距离和圆的问题?
为什么这个观察结果对计算有用呢?随机游动的密度与热扩散有关，热扩散受一阶偏微分方程控制，可以通过求解稀疏线性系统很好地逼近。作者的重要见解是，广泛的线性算子可以用于计算具有所需梯度方向(但梯度长度不同)的函数。
对于任何这样的函数，只需将梯度归一化，然后对其积分，就可以计算出距离。积分相当于解决另一个稀疏线性系统。这意味着测地线距离可以通过求解两个(相关的)稀疏线性系统，加上计算中间函数的梯度并将其归一化来计算。注意这个问题的非线性是如何被推到标准化一组向量的琐碎步骤中，而所有的全局计算都是线性的。
最后，将测地线路径的计算问题转化为一个稀疏线性系统的解，还有另一个非常可取的特点:最耗时的部分是分解系统矩阵的步骤。这种分解可用于域上的任意距离计算。所以所有国王需要的是一个线性系统的三角形因子，然后每个测地线圆几乎可以瞬间计算出来。
数字图书馆是由计算机协会出版的。版权所有©2017 ACM, Inc.
没有发现记录