On Approximating the Weighted Region Problem in Square Tessellations
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911969076838400 |
|---|---|
| author | Kakimura, Naonori Katsu, Rio |
| author_facet | Kakimura, Naonori Katsu, Rio |
| contents | The weighted region problem is the problem of finding the weighted shortest path on a plane consisting of polygonal regions with different weights. For the case when the plane is tessellated by squares, we can solve the problem approximately by finding the shortest path on a grid graph defined by placing a vertex at the center of each grid. In this note, we show that the obtained path admits $(\sqrt{2}+1)$-approximation. This improves the previous result of $2\sqrt{2}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_18758 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Approximating the Weighted Region Problem in Square Tessellations Kakimura, Naonori Katsu, Rio Computational Geometry Data Structures and Algorithms The weighted region problem is the problem of finding the weighted shortest path on a plane consisting of polygonal regions with different weights. For the case when the plane is tessellated by squares, we can solve the problem approximately by finding the shortest path on a grid graph defined by placing a vertex at the center of each grid. In this note, we show that the obtained path admits $(\sqrt{2}+1)$-approximation. This improves the previous result of $2\sqrt{2}$. |
| title | On Approximating the Weighted Region Problem in Square Tessellations |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.18758 |