Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414235 | Computational Geometry | 2014 | 16 Pages |
Abstract
We present an algorithm for approximating geodesic distances on 2-manifolds in R3R3. Our algorithm works on an ε-sample of the underlying manifold and computes approximate geodesic distances between all pairs of points in this sample. The approximation error is multiplicative and depends on the density of the sample. For an ε-sample S , the algorithm has a near-optimal running time of O(|S|2log|S|)O(|S|2log|S|), an optimal space requirement of O(|S|2)O(|S|2), and approximates the geodesic distances up to a factor of 1−O(ε) and (1−O(ε))−1(1−O(ε))−1.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Christian Scheffer, Jan Vahrenhold,