On approximating shortest paths in weighted triangular tessellations Article Swipe

MAKE IMPACT

Prosenjit Bose , Guillermo Esteban , David Orden , Rodrigo I. Silveira · YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.1016/j.artint.2023.103898

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 $ \mathit{SP_w}(s,t) $, which is a shortest path from $ s $ to $ t $ in the space; a weighted shortest vertex path $ \mathit{SVP_w}(s,t) $, which is an any-angle shortest path; and a weighted shortest grid path $ \mathit{SGP_w}(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. [Path-length analysis for grid-based path planning. Artificial Intelligence, 301:103560, 2021], we prove upper and lower bounds on the ratios $ \frac{\lVert \mathit{SGP_w}(s,t)\rVert}{\lVert \mathit{SP_w}(s,t)\rVert} $, $ \frac{\lVert \mathit{SVP_w}(s,t)\rVert}{\lVert \mathit{SP_w}(s,t)\rVert} $, $ \frac{\lVert \mathit{SGP_w}(s,t)\rVert}{\lVert \mathit{SVP_w}(s,t)\rVert} $, 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 $ \frac{\lVert \mathit{SGP_w}(s,t)\rVert}{\lVert \mathit{SP_w}(s,t)\rVert} = \frac{2}{\sqrt{3}} \approx 1.15 $ in the worst case, and this is tight. As a corollary, for the weighted any-angle path $ \mathit{SVP_w}(s,t) $ we obtain the approximation result $ \frac{\lVert \mathit{SVP_w}(s,t)\rVert}{\lVert \mathit{SP_w}(s,t)\rVert} \lessapprox 1.15 $.

Type

preprint

Language

en

Landing Page

https://doi.org/10.1016/j.artint.2023.103898

OA Status

hybrid

References

40

Related Works

10

OpenAlex ID

https://openalex.org/W4226303121

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4226303121

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.1016/j.artint.2023.103898

Digital Object Identifier

Title

On approximating shortest paths in weighted triangular tessellations

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2023

Year of publication

Publication date

2023-03-05

Full publication date if available

Authors

Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo I. Silveira

List of authors in order

Landing page

https://doi.org/10.1016/j.artint.2023.103898

Publisher landing page

Open access

Yes

Whether a free full text is available

OA status

hybrid

Open access status per OpenAlex

OA URL

https://doi.org/10.1016/j.artint.2023.103898

Direct OA link when available

Concepts

Combinatorics, Shortest path problem, Vertex (graph theory), Tessellation (computer graphics), Path (computing), Mathematics, Hexagonal tiling, Space (punctuation), Discrete mathematics, Computer science, Grid, Geometry, Operating system, Programming language, Graph

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

References (count)

40

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload