Approximating geodesic distances on 2-manifolds in R-3: The weighted case

作者：Scheffer Christian^*; Vahrenhold Jan

来源：Computational Geometry-Theory and Applications, 2014, 47(8): 789-808.

DOI：10.1016/j.comgeo.2014.04.003

• Weighted geodesic distances
• Manifold reconstruction
• Approximation algorithm

We present the first algorithm for approximating weighted geodesic distances on 2-manifolds in R-3. Our algorithm works on a weighted epsilon-sample S of the underlying manifold and computes approximate geodesic distances between all pairs of points in S. The approximation error is multiplicative and depends on the density of the sample. The algorithm has a running time of O(vertical bar S vertical bar(2.25) log(2) vertical bar S vertical bar) and an optimal space requirement of O(vertical bar S vertical bar(2)); the approximation error is bounded by 1 +/- O(epsilon). As a result of independent and possibly practical interest, we develop the first technique to efficiently approximate the sampling density epsilon of S; this algorithm naturally carries over to the unweighted case.

• 出版日期2014-9