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Β ππ_π€(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