In this paper, we consider the Weighted Region Problem. In the Weighted Region Problem, the length of a path is defined as the sum of the weights of the subpaths within each region, where the weight of a subpath is its Euclidean length multiplied by a weight \(\alpha \geq 0\) depending on the region. We study a restricted version of the problem of determining shortest paths through a single weighted rectangular region. We prove that even this very restricted version of the problem is unsolvable within the Algebraic Computation Model over the Rational Numbers (ACM\(\mathbb{Q}\)). On the positive side, we provide the equations for the shortest paths that are computable within the ACM\(\mathbb{Q}\). Additionally, we provide equations for the bisectors between regions of the Shortest Path Map for a source point on the boundary of (or inside) the rectangular region.
Proc. 36th Canadian Conference on Computational Geometry (CCCG), 2024
@inproceedings{wrp2024,
author = {de Berg, Sarita and Esteban, Guillermo and I. Silveira, Rodrigo and Staals, Frank},
title = {Exact solutions to the Weighted Region Problem},
booktitle = {Proc. 36th Canadian Conference on Computational Geometry (CCCG)},
year = {2024},
location = {St. Catharines, Canada},
numpages = {8},
category = {wrp},
}
Abstr. 40th European Workshop on Computational Geometry (EuroCG), 2024
@article{wrp_eurocg,
author = {de Berg, Sarita and Esteban, Guillermo and I. Silveira, Rodrigo and Staals, Frank},
title = {Exact solutions to the Weighted Region Problem},
journal = {Abstr. 40th European Workshop on Computational Geometry (EuroCG)},
year = {2024},
location = {Ioannina, Greece},
numpages = {8},
category = {wrp},
project = {wrp2024},
}