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

We present the first algorithm for approximating weighted geodesic distances on 2-manifolds in R3R3. Our algorithm works on a weighted ε-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(|S|2.25log2|S|)O(|S|2.25log2|S|) and an optimal space requirement of O(|S|2)O(|S|2); the approximation error is bounded by 1±O(ε)1±O(ε). As a result of independent and possibly practical interest, we develop the first technique to efficiently approximate the sampling density ε of S; this algorithm naturally carries over to the unweighted case.