Simple, Robust, Constant-Time Bounds on Surface Geodesic Distances using Point Landmarks

David Bommes, Tobias Ritschel und Thomas Schultz (Editoren)
In proceedings of Vision, Modeling & Visualization, 2015
 

Abstract

In this paper we exploit redundant information in geodesic distance fields for a quick approximation of all-pair distances. Starting with geodesic distance fields of equally distributed landmarks we analyze the lower and upper bound resulting from the triangle inequality and show that both bounds converge reasonably fast to the original distance field. The lower bound has itself a bounded relative error, fulfills the triangle equation and under mild conditions is a distance metric. While the absolute error of both bounds is smaller than the maximal landmark distances, the upper bound often exhibits smaller error close to the cut locus. Both the lower and upper bound are simple to implement and quickly to evaluate with a constant-time effort for point-to-point distances, which are often required by various algorithms.

Bilder

Paper herunterladen

Paper herunterladen

Zusätzliches Material

Bibtex

@INPROCEEDINGS{BK2015,
     author = {Burghard, Oliver and Klein, Reinhard},
     editor = {Bommes, David and Ritschel, Tobias and Schultz, Thomas},
      title = {Simple, Robust, Constant-Time Bounds on Surface Geodesic Distances using Point Landmarks},
    journal = {Vision, Modeling, and Visualization},
  booktitle = {Vision, Modeling {\&} Visualization},
       year = {2015},
   abstract = {In this paper we exploit redundant information in geodesic distance fields for a quick approximation
               of all-pair distances. Starting with geodesic distance fields of equally distributed landmarks we
               analyze the lower and upper bound resulting from the triangle inequality and show that both bounds
               converge reasonably fast to the original distance field. The lower bound has itself a bounded
               relative error, fulfills the triangle equation and under mild conditions is a distance metric. While
               the absolute error of both bounds is smaller than the maximal landmark distances, the upper bound
               often exhibits smaller error close to the cut locus. Both the lower and upper bound are simple to
               implement and quickly to evaluate with a constant-time effort for point-to-point distances, which
               are often required by various algorithms.},
       isbn = {978-3-905674-95-8},
        url = {https://diglib.eg.org/handle/10.2312/vmv20151253},
        doi = {10.2312/vmv.20151253}
}