On approximating shortest paths in weighted triangular tessellations

11/27/2021
βˆ™
by   Prosenjit Bose, et al.
βˆ™
0
βˆ™

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 𝑆𝑃_𝑀(s,t), which is a shortest path from s to t in the space; a weighted shortest vertex path 𝑆𝑉𝑃_𝑀(s,t), which is a shortest path where the vertices of the path are vertices of the tessellation; and a weighted shortest grid path 𝑆𝐺𝑃_𝑀(s,t), which is a shortest path whose edges are edges of the tessellation. The ratios ‖𝑆𝐺𝑃_𝑀(s,t)β€–/‖𝑆𝑃_𝑀(s,t)β€–, ‖𝑆𝑉𝑃_𝑀(s,t)β€–/‖𝑆𝑃_𝑀(s,t)β€–, ‖𝑆𝐺𝑃_𝑀(s,t)β€–/‖𝑆𝑉𝑃_𝑀(s,t)β€– provide estimates on the quality of the approximation. Given any arbitrary weight assignment to the faces of a triangular tessellation, we prove upper and lower bounds on the estimates that are independent of the weight assignment. Our main result is that ‖𝑆𝐺𝑃_𝑀(s,t)β€–/‖𝑆𝑃_𝑀(s,t)β€– = 2/√(3)β‰ˆ 1.15 in the worst case, and this is tight.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset