Communications of the ACM
Home/Magazine Archive/November 2017 (Vol. 60, No. 11)/Technical Perspective: Exploring a Kingdom By Geodesic.../Full Text
Research highlights
Technical Perspective: Exploring a Kingdom By Geodesic Measures
Once upon a time, there was a particularly generous king. He decided to give all of his people a share of his land. Any family owning a house would have to mark the center of their land with a stone. Then the ruling said that every point they could reach within 1,000 steps from the mark stone would belong to them.
Initially, the king was praised for the simplicity and clarity of his ruling. Yet, as most new landowners decided to build a fence around their property they soon realized that determining the location of the fence was frustratingly difficult. Any point that was reached after walking 1,000 steps was part of the property, sure; but how would one have to walk to reach a point that was as far away from the stone as possible?
Luckier landowners lived in flat regions, where walking along a straight line (for example, walking toward any landmark further away than 1,000 steps) would always reach a point on the boundary of the land. Landowners in hilly regions had a problem. They needed to find a path that was the equivalent of a straight line. Such paths are now known as geodesics—the name indeed relating to the problem of measuring the earth. In today's language, the land assigned to each family is a geodesic disk. And it should come as no surprise that the distance between two points in curved domains is a fundamental problem with numerous applications in science and engineering.
So, how would we solve the problem of computing geodesic paths, distances, and circles on a digital computer? Let's assume the smooth terrain is approximated as a triangulation. The shortest path from a vertex of this triangulation to all other vertices along the edges of the triangulation can be computed using Dijkstra's algorithm. While this provides an efficient solution to the problem of finding a path, traveling only along the edges of the triangles will not yield the shortest possible path. A better option is tracking how a wavefront emanates from a source vertex, the so-called fast marching method.
Unfortunately, this method may fail to provide shortest paths for certain surfaces and shapes of triangles. It turns out the problem of shortest paths along a piecewise linear surface has a superquadratic worst-case complexity, and algorithms establishing this complexity are surprisingly complicated. The most recent algorithms of this kind have much better asymptotic complexity in common practical cases, yet they are still significantly more complex than a simple graph traversal such as Dijkstra's.
The approach by Crane, Weischedel, and Wardetzky in the following paper may be related to what the landowners could have observed and exploited: assume one would start from the mark stone, walk 1,000 random steps, and mark the endpoint of this walk with a pebble. Over many repetitions of this exercise a distribution of pebbles on the land emerges: closer to the mark stone the pattern is denser, and fewer and fewer pebbles are found further away. As it turns out, starting at the mark stone and always walking in the direction of fewer stones will result in the desired geodesic path. Or, in more recent language, the gradient of the probability density function of a random walk is parallel to geodesics.
How would we solve the problem of computing geodesic paths, distances, and circles on a digital computer?
Now, why is this observation useful for computation? The density of random walks is related to heat diffusion, and heat diffusion is governed by a first-order partial differential equation, which can be well approximated by solving a sparse linear system. The important insight from the authors is that a wide range of linear operators can be used to compute functions with the desired gradient directions (yet different gradient lengths)
Given any such function, distances can be computed by simply normalizing the gradients and then integrating them. Integration amounts to solving another sparse linear system. Together this means geodesic distances can be computed by solving two (related) sparse linear systems, plus computing the gradients of the intermediate function and normalizing them. Note how the non-linearity of the problem is pushed into the trivial step of normalizing a set of vectors, while all global computations are linear.
And lastly, turning the problem of computing geodesic paths to the solution of a sparse linear system has another very desirable feature: the most time-consuming part lies in the step of factorizing the system matrix. This factorization can be reused for arbitrary distance computations on the domain. So all the king would have needed were the triangular factors of a linear system, and then each geodesic circle could have been computed almost instantaneously.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2017 ACM, Inc.
No entries found