On Approximating the Weighted Region Problem in Square Tessellations

Autor:	Kakimura, Naonori, Katsu, Rio
Rok vydání:	2024
Předmět:	Computer Science - Computational Geometry Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	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}$.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2407.18758 Zobrazit plný text záznamu View this record from Arxiv