On Approximating the Weighted Region Problem in Square Tessellations
<|reference_start|>On Approximating the Weighted Region Problem in Square Tessellations: 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}$.<|reference_end|>
@article{kakimura2024on,
    title={On Approximating the Weighted Region Problem in Square Tessellations},
    author={Naonori Kakimura and Rio Katsu},
    journal={arXiv preprint arXiv:2407.18758},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.18758},
    primaryClass={cs.CG cs.DS}
}