# Approximate Distance Queries for Weighted Polyhedral Surfaces

Hristo N. Djidjev and Christian Sommer
ESA 2011 - 19th European Symposium on Algorithms (pp. 579-590)

Let $$P$$ be a planar polyhedral surface consisting of $$n$$ triangular faces, each assigned with a positive weight. The weight of a path $$p$$ on $$P$$ is defined as the weighted sum of the Euclidean lengths of the portions of $$p$$ in each face multiplied by the corresponding face weights. We show that, for every $$0 \lt \epsilon \lt 1$$, there exists a data structure, termed distance oracle, computable in time $$O(n\epsilon^{-2}\log^3(n/\epsilon)\log^2(1/\epsilon))$$ and of size $$O(n\epsilon^{-3/2}\log^2(n/\epsilon)\log(1/\epsilon))$$, such that $$(1+\epsilon)$$-approximate distance queries in $$P$$ can be answered in time $$O(\epsilon^{-1}\log(1/\epsilon) + \log\log n)$$. As in previous work (Aleksandrov, Maheshwari, and Sack (J. ACM 2005) and others), the big-$$O$$ notation hides constants depending logarithmically on the ratio of the largest and smallest face weights and reciprocally on the sine of the smallest angle of $$P$$. The tradeoff between space and query time of our distance oracle is a significant improvement in terms of $$n$$ over the previous best tradeoff obtained by a distance oracle of Aleksandrov, Djidjev, Guo, Maheshwari, Nussbaum, and Sack (Discrete Comput. Geom. 2010), which requires space roughly quadratic in $$n$$ for a comparable query time.

@inproceedings{DS11,
author	   = {Hristo Djidjev and Christian Sommer},
title	   = {Approximate Distance Queries
for Weighted Polyhedral Surfaces},
booktitle = {19th European Symposium on Algorithms (ESA)},
year	   = {2011},
pages	   = {579--590},
url       = {http://dx.doi.org/10.1007/978-3-642-23719-5_49},
doi       = {10.1007/978-3-642-23719-5_49},
}


Official version
Local version (215.6 KB)

HomePublications → Approximate Distance Queries for Weighted Polyhedral Surfaces