Approximations of Geodesic Distances for Incomplete Triangular Manifolds

  1. (PDF, 392 KB)
AuthorSearch for: ; Search for: ; Search for: ; Search for:
ConferenceCanadian Conference on Computational Geometry, August 20-22, 2007., Ottawa, Ontario, Canada
AbstractWe present a heuristic algorithm to compute approximate geodesic distances on 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). Wederive a new heuristic method to add an object to the embedding computed via least-squares MDS.
Publication date
AffiliationNRC Institute for Information Technology; National Research Council Canada
Peer reviewedNo
NRC number49831
NPARC number5764997
Export citationExport as RIS
Report a correctionReport a correction
Record identifier8eae5e8b-63de-4126-a5bf-5078a6d9025d
Record created2009-03-29
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)
Date modified: