Exact solutions to the Weighted Region Problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908948351680512 |
|---|---|
| author | de Berg, Sarita Esteban, Guillermo Silveira, Rodrigo I. Staals, Frank |
| author_facet | de Berg, Sarita Esteban, Guillermo Silveira, Rodrigo I. Staals, Frank |
| contents | 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 $ α\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 (ACMQ). On the positive side, we provide the equations for the shortest paths that are computable within the ACMQ. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_12028 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exact solutions to the Weighted Region Problem de Berg, Sarita Esteban, Guillermo Silveira, Rodrigo I. Staals, Frank Computational Geometry 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 $ α\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 (ACMQ). On the positive side, we provide the equations for the shortest paths that are computable within the ACMQ. 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. |
| title | Exact solutions to the Weighted Region Problem |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2402.12028 |