2007-12-01
Approximations of geodesic distances for incomplete triangular manifolds
Publication
Publication
Presented at the
19th Annual Canadian Conference on Computational Geometry, CCCG 2007 (August 2007)
We present a heuristic algorithm to compute approximate geodesic distances on a triangular manifold S containing n vertices with partially missing data. The proposed method computes an approximation of the geodesic distance between two vertices pi and pj on S and provides an upper bound of the geodesic distance that is shown to be optimal in the worst case. This yields a relative error bound of the estimate that is worst-case optimal. The algorithm approximates the geodesic distance without trying to reconstruct the missing data by embedding the surface in a low dimensional space via multi-dimensional scaling (MDS). We derive a new heuristic method to add an object to the embedding computed via least-squares MDS.
Additional Metadata | |
---|---|
19th Annual Canadian Conference on Computational Geometry, CCCG 2007 | |
Organisation | Carleton University |
Azouz, Z.B. (Zouhour Ben), Bose, P, Shu, C. (Chang), & Wuhrer, S. (Stefanie). (2007). Approximations of geodesic distances for incomplete triangular manifolds. Presented at the 19th Annual Canadian Conference on Computational Geometry, CCCG 2007.
|