Exact solutions to the Weighted Region Problem

Frank Staals; Guillermo Esteban; Rodrigo I. Silveira; Sarita de Berg

arxiv: 2402.12028 · v4 · submitted 2024-02-19 · 💻 cs.CG

Exact solutions to the Weighted Region Problem

Sarita de Berg , Guillermo Esteban , Rodrigo I. Silveira , Frank Staals This is my paper

Pith reviewed 2026-05-24 04:08 UTC · model grok-4.3

classification 💻 cs.CG

keywords Weighted Region ProblemShortest PathsUnsolvabilityAlgebraic Computation ModelComputational GeometryRectangular RegionShortest Path Map

0 comments

The pith

The shortest path through a single weighted rectangle is unsolvable in the algebraic computation model over the rationals.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines shortest paths in the weighted region problem when restricted to one rectangular region of uniform weight. It proves this minimal case cannot be solved exactly inside the Algebraic Computation Model over the Rational Numbers. The model treats only certain algebraic expressions as valid exact answers. The authors also derive the equations that remain computable inside the model and the equations that describe bisectors of the shortest path map.

Core claim

Even the restricted problem of finding shortest paths through a single weighted rectangular region is unsolvable within the Algebraic Computation Model over the Rational Numbers (ACMQ). Equations for the computable shortest paths and for the bisectors between regions of the Shortest Path Map are provided.

What carries the argument

The Algebraic Computation Model over the Rational Numbers (ACMQ) applied to shortest paths in a single weighted rectangular region.

If this is right

Exact solutions remain impossible for the single-rectangle case under the stated model.
Only paths whose bend points satisfy the supplied equations can be computed inside ACMQ.
The bisectors of the shortest path map admit explicit algebraic descriptions within ACMQ.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Practical weighted-region path planners will need to use approximations or switch to a different model of exactness.
The same unsolvability technique may apply to other low-complexity weighted geometric problems.
Alternative models that permit transcendental operations could restore exact solvability for this instance.

Load-bearing premise

That the Algebraic Computation Model over the Rational Numbers is the correct standard for deciding whether an exact solution exists.

What would settle it

An algorithm that produces the exact shortest-path length or bend points for the single-rectangle case using only the field operations and root extractions allowed by ACMQ would falsify the unsolvability result.

Figures

Figures reproduced from arXiv: 2402.12028 by Frank Staals, Guillermo Esteban, Rodrigo I. Silveira, Sarita de Berg.

**Figure 3.** Figure 3: Illustration of the notation used for π5(s, t) in Lemma 6. Note that we do not take into account the case where α = 1 since in that case the shortest path from s to t is simply a straight-line segment. We frequently use these equations in the rest of this section to determine the lengths of the paths πi(s, t), for all i. ▶ Lemma 5. The length of π2(s, t) is given by d2(s, t) = α(sx − tx) + √ 1 − α2ty. Proo… view at source ↗

**Figure 4.** Figure 4: Illustration of the notation used for π8(s, t) in Lemma 9. ▶ Lemma 8. The length of π7(s, t) is given by d7(s, t) = √ α2 − 1sx + 1 + p t 2 x + (ty + 1)2. Proof. Let (0, b1) be the point where π7(s, t) leaves R for the first time, i.e., the first vertex of π7(s, t). Since b1 < 0, and sx > 0, we obtain the coordinates of this first vertex by using Equation (3): tan θc = |b1| |sx| = −b1 sx = 1 √ α2 − 1 ⇒ b1 =… view at source ↗

read the original abstract

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 (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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves that shortest paths through even one weighted rectangle are unsolvable in ACMQ while supplying the explicit equations that stay inside the model.

read the letter

The main takeaway is that exact shortest paths in the weighted region problem remain out of reach even when restricted to a single rectangle, at least inside the Algebraic Computation Model over the Rationals. The authors show this negative result and then give the concrete equations for the paths and for the bisectors in the shortest-path map when the source is on or inside the rectangle boundary. That combination of a clean negative result plus usable equations is the useful part. The unsolvability claim for the single-rectangle case does not appear in the earlier literature they cite, so the negative result is new on its own terms. The equations themselves look like the sort of algebraic setup one would expect from Snell's law style refraction at the boundaries, and they are presented as ACMQ-computable, which matches the model they chose for the impossibility proof. The soft spot is the model choice itself. ACMQ is stricter than the real-RAM or algebraic computation tree models that are more common in computational geometry, so the unsolvability statement is tied to that particular formalization. If the goal is to say something about what counts as an exact solution in practice, the reader has to accept that ACMQ is the right yardstick; the paper does not spend much time justifying why other models are less relevant here. The proof details are not visible in the abstract, but the claim is stated directly and the positive equations are supplied, so the central argument is at least internally consistent. This is a paper for people working on exact algorithms for terrain navigation or motion planning who care about the precise computational boundaries of the weighted region problem. It is narrow enough that it will not change daily practice, but the negative result plus the explicit equations make it worth a serious referee's time to check the algebra and the model assumptions.

Referee Report

2 major / 1 minor

Summary. The paper studies a restricted single-rectangle case of the Weighted Region Problem and claims to prove that determining the shortest path is unsolvable in the Algebraic Computation Model over the Rational Numbers (ACMQ). On the positive side, it supplies explicit ACMQ-computable equations for the shortest paths and for the bisectors of the Shortest Path Map when the source lies on the boundary or inside the rectangle.

Significance. If the unsolvability result holds under the stated model, the work supplies a formal negative result together with constructive equations, which could help delineate the boundary between exactly solvable and approximable instances in weighted geometric shortest-path problems. The explicit provision of ACMQ-computable equations is a concrete positive contribution that can be directly used in implementations restricted to field operations over Q.

major comments (2)

[Abstract / §2] Abstract and the definition of ACMQ (presumably §2): the central unsolvability claim is predicated on ACMQ being the appropriate formalization of 'exact' solvability. The manuscript does not compare ACMQ to the algebraic computation tree model or real-RAM model standard in computational geometry, both of which permit root extractions of arbitrary degree; without this comparison the transfer of the unsolvability result to the usual notion of exact geometric computation is not established.
[Proof of unsolvability (location not numbered in excerpt)] The algebraic unsolvability argument (the proof referenced in the abstract): the manuscript states that a proof exists and supplies equations, yet the derivation showing that the critical point equations lie outside ACMQ is not fully expanded or verified in the provided text; this step is load-bearing for the negative result.

minor comments (1)

[Abstract] Notation for the weight parameter α is introduced without an explicit statement of its domain (α ≥ 0) in the first paragraph of the abstract; a parenthetical reminder would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The comments highlight two areas where the manuscript can be strengthened: providing context for the ACMQ model relative to other standard models in computational geometry, and expanding the unsolvability proof. We address both points below and will incorporate revisions accordingly.

read point-by-point responses

Referee: [Abstract / §2] Abstract and the definition of ACMQ (presumably §2): the central unsolvability claim is predicated on ACMQ being the appropriate formalization of 'exact' solvability. The manuscript does not compare ACMQ to the algebraic computation tree model or real-RAM model standard in computational geometry, both of which permit root extractions of arbitrary degree; without this comparison the transfer of the unsolvability result to the usual notion of exact geometric computation is not established.

Authors: We agree that the manuscript would benefit from an explicit comparison of ACMQ to the algebraic computation tree model and real-RAM model. In the revised version, we will add a subsection in §2 that defines ACMQ as the model restricted to the field operations (+, −, ×, ÷) over ℚ, contrasting it with models that additionally permit root extractions of arbitrary degree. We will note that our unsolvability result is specific to ACMQ and does not directly apply to models allowing radicals, thereby clarifying the scope and transferability of the negative result. revision: yes
Referee: [Proof of unsolvability (location not numbered in excerpt)] The algebraic unsolvability argument (the proof referenced in the abstract): the manuscript states that a proof exists and supplies equations, yet the derivation showing that the critical point equations lie outside ACMQ is not fully expanded or verified in the provided text; this step is load-bearing for the negative result.

Authors: We acknowledge that the derivation establishing unsolvability in ACMQ requires fuller expansion for verification. In the revision, we will provide a detailed, step-by-step expansion of the argument in the relevant section (currently referenced in the abstract). This will include showing how the critical-point equations reduce to a polynomial system whose solutions cannot be obtained from rational numbers using only the field operations of ACMQ, with explicit verification that no sequence of additions, multiplications, and divisions suffices. revision: yes

Circularity Check

0 steps flagged

No significant circularity in unsolvability proof

full rationale

The paper's central result is a formal proof that the single-rectangle weighted-region shortest-path problem is unsolvable in the explicitly defined ACMQ model, together with explicit ACMQ-computable equations for the paths and bisectors. No derivation step reduces by construction to its own inputs, no parameters are fitted and then relabeled as predictions, and no load-bearing self-citations or uniqueness theorems imported from the authors' prior work appear in the abstract or described claims. The choice of ACMQ is an explicit modeling premise rather than a self-referential loop, rendering the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the standard definition of the ACMQ model and Euclidean path costs; no free parameters or invented entities are introduced in the abstract.

axioms (1)

standard math Euclidean distance and algebraic operations over rationals define the allowed computations in ACMQ
Invoked when stating unsolvability within ACMQ.

pith-pipeline@v0.9.0 · 5672 in / 1071 out tokens · 46895 ms · 2026-05-24T04:08:40.549903+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

1 extracted references · 1 canonical work pages

[1]

Aleksandrov, M

1 L. Aleksandrov, M. Lanthier, A. Maheshwari, and J.-R. Sack. Anε-approximation algorithm for weighted shortest paths on polyhedral surfaces. InScandinavian Workshop on Algorithm Theory, pages 11–22. Springer, 1998. 2 L. Aleksandrov, A. Maheshwari, and J.-R. Sack. Approximation algorithms for geometric shortest path problems. InProceedings of the Thirty-S...

work page doi:10.1016/j.comgeo.2014.02.004 1998

[1] [1]

Aleksandrov, M

1 L. Aleksandrov, M. Lanthier, A. Maheshwari, and J.-R. Sack. Anε-approximation algorithm for weighted shortest paths on polyhedral surfaces. InScandinavian Workshop on Algorithm Theory, pages 11–22. Springer, 1998. 2 L. Aleksandrov, A. Maheshwari, and J.-R. Sack. Approximation algorithms for geometric shortest path problems. InProceedings of the Thirty-S...

work page doi:10.1016/j.comgeo.2014.02.004 1998