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

Burghard, Oliver; Klein, Reinhard

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

Files

017-024.pdf (2.8 MB)

Date

2015

Authors

Burghard, Oliver
Klein, Reinhard

Publisher

The Eurographics Association

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.

        @inproceedings{10.2312:vmv.20151253
,
booktitle = {Vision, Modeling & Visualization
},
editor = {David Bommes and Tobias Ritschel and Thomas Schultz
},
title = {{Simple, Robust, Constant-Time Bounds on Surface Geodesic Distances using Point Landmarks
}},
author = {Burghard, Oliver and 
Klein, Reinhard
},
year = {2015
},
publisher = {The Eurographics Association
},
ISBN = {978-3-905674-95-8
},
DOI = {10.2312/vmv.20151253
}
}