On approximating shortest paths in weighted triangular tessellations

We study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessellation approximates the 2-dimensional space, we study three types of shortest paths: a weighted shortest path SPw(s, t), which is a shortest path from s to t in the space; a weighted shortest vertex path SVPw(s, t), which is an any-angle shortest path; and a weighted shortest grid path SGPw(s, t), which is a shortest path whose edges are edges of the tessellation. Given any arbitrary weight assignment to the faces of a triangular tessellation, thus extending recent results by Bailey et al. (2021) [6], we prove upper and lower bounds on the ratios IISGPw(s,t)IIIISPw(s,t)II, IISVPwIISPw(s,t(s,t)II)II, IISGPw(s,t)II IISVPw(s,t)II, which provide estimates on the quality of the approximation. It turns out, surprisingly, that our worst-case bounds are independent of any weight assignment. Our main result is that IISGPw(s,t)II IISPw(s,t)II= J23,,; 1.15 in the worst case, and this is tight. As a corollary, for the weighted any-angle path SVPw(s, t) we obtain the approximation result IISVPw(s,t)II IISPw(s,t)II <= 1.15.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons .org /licenses /by-nc -nd /4 .0/).

Automated summary

We study the quality of weighted shortest paths in a discretized 2-dimensional space using a weighted triangular tessellation. We evaluate the tessellation's approximation of the space by studying three types of shortest paths: weighted shortest path, weighted shortest vertex path, and weighted shortest grid path. We provide estimates on the quality of the approximation and prove that our worst-case bounds are independent of any weight assignment.