Optimal 3D Road Alignment on Topographic Surfaces: A Convergent Dynamic Programming Approach

Anna A. Gorbunova; Majid E. Abbasov

REVIEW 2 major objections 2 minor 30 references

Optimal 3D Road Alignment on Topographic Surfaces: A Convergent Dynamic Programming Approach

T0 review · 2 major / 2 minor · reviewed 2026-05-22 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗

Pith's one-line read A dynamic programming scheme for optimal 3D road paths on terrain converges to the global optimum when vertical grid steps shrink faster than horizontal ones.

desk verdict A DP scheme for 3D road alignment with a power-law convergence condition and local-search speedup that adds a formal result to this applied problem. read the letter →

arxiv 2503.10922 v2 submitted 2025-03-13 math.OC

Majid E. Abbasov , Anna A. Gorbunova This is my paper

classification math.OC

keywords optimalroadalignmentdynamicprogrammingconvergenceproof3DterraincalculusofvariationsArzelà–Ascolitheorempathoptimizationdiscretizationerror

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper formulates the 3D road alignment problem as minimization of an integral cost functional that accounts for material delivery and construction expenses over a topographic surface. It establishes existence of a global minimizer through the Arzelà–Ascoli theorem applied to suitable function spaces. A dynamic programming algorithm is then constructed on a discretized grid, and a convergence theorem is proved: the piecewise-linear solutions approach the true optimum precisely when the vertical discretization step decays faster than the horizontal step according to a power-law relation. A local-search variant is added to bring the computational cost down to nearly quadratic in the horizontal step size. Tests on sample 2D and 3D terrains confirm that the method matches the accuracy of the Ritz method while running substantially faster.

What carries the argument

Dynamic programming on a rectangular grid whose vertical and horizontal step sizes obey a power-law relation that controls the approximation error of the piecewise-linear paths.

What would settle it

Compute the dynamic-programming solutions on a terrain whose optimal path is known analytically and verify whether the computed paths stop converging to the known optimum once the vertical step is no longer required to decay faster than the horizontal step.

Watch

Extended reading notes

Core claim

The sequence of piecewise-linear solutions generated by the dynamic programming scheme converges to the true optimum of the road alignment problem when the vertical discretization step decays faster than the horizontal one, under the regularity conditions that allow the Arzelà–Ascoli theorem to guarantee a global minimizer.

Load-bearing premise

The cost functional and terrain must meet regularity conditions strong enough for the Arzelà–Ascoli theorem to guarantee existence of a minimizer, and the power-law relation between step sizes must be sufficient to drive the dynamic-programming error to zero.

Editorial extensions

If this is right

Global optimality of the computed road can be approached arbitrarily closely by refining the grid according to the stated power-law relation.
The local-search modification reduces runtime to nearly quadratic in the horizontal step while preserving the convergence guarantee.
The same discretization condition applies equally to the two-dimensional and three-dimensional versions of the problem.
The computed paths achieve accuracy comparable to the Ritz method at lower computational cost on the tested terrains.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same power-law control on discretization steps may be portable to other variational path problems solved by dynamic programming on surfaces.
Implementation in civil-engineering software would require only that the grid generator enforce the vertical-to-horizontal step ratio at each refinement level.
The framework supplies a concrete, testable benchmark against which heuristic road-design algorithms can be compared for global optimality.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The main takeaway is a dynamic programming scheme for finding optimal 3D road trajectories on variable terrain that comes with a convergence proof tied to a power-law relation on the discretization steps. The authors establish existence of the minimizer using the Arzela-Ascoli theorem on the set of admissible paths. They then discretize with DP and show that if the vertical step size goes to zero faster than the horizontal one in a specific power-law way, the piecewise linear solutions converge to the optimum. They also introduce a local search step that brings the complexity down to O(τ^{-2-ε}). This is new because the power-law condition and the accelerated version are not in the prior heuristics or Ritz approaches they cite. The numerical experiments on 2D and 3D terrains confirm that accuracy is comparable to the Ritz method but with reduced processing time, which is a clear practical gain. The soft spots are in the proof details. The claim that the power-law controls the approximation error is central, and while the abstract states it, the full error analysis would need to be checked for any gaps in bounding the difference between discrete and continuous solutions. The local search is said to maintain the properties, but how it avoids suboptimal traps in the grid search could be spelled out more. The work is aimed at engineers and applied optimizers dealing with road design on topography. A reader looking for a method with both theory and implementation would find it useful. I recommend sending it for peer review. The combination of a formal convergence result and efficiency improvement makes it worth the time of referees.

Referee Report

2 major / 2 minor

Summary. The manuscript develops a variational formulation for optimal 3D road alignment on topographic surfaces, defining an integral cost that accounts for material and construction expenses. Existence of a global minimizer is asserted via the Arzelà–Ascoli theorem on the admissible set. A dynamic programming discretization is introduced whose piecewise-linear solutions are claimed to converge to the optimum when vertical and horizontal grid steps obey a specific power-law relation (vertical decaying faster). A local-search acceleration is proposed that reduces complexity to O(τ^{-2-ε}), and numerical tests on 2D/3D terrains are reported to match Ritz-method accuracy at lower cost.

Significance. If the convergence statement is rigorously established, the work supplies a theoretically grounded alternative to heuristic path planners for road design, together with an explicit complexity improvement. The combination of existence proof, discretization analysis, and practical timing results would be a useful contribution to applied optimal control and infrastructure optimization.

major comments (2)

[Convergence theorem / proof of DP convergence] The central convergence claim (piecewise-linear DP solutions converge under the stated power-law relation between vertical and horizontal steps) is load-bearing. The manuscript must supply the explicit error estimate showing that the faster decay of the vertical step controls the total approximation error; without this quantitative bound the power-law condition remains an assertion rather than a verified sufficient condition.
[Existence section / admissible set definition] The regularity hypotheses placed on the cost functional and terrain (needed for Arzelà–Ascoli compactness) are not stated explicitly. These hypotheses must be listed and verified to be compatible with the admissible set before the existence result can be accepted as supporting the subsequent numerical scheme.

minor comments (2)

Define the symbols τ and ε at first use and keep the notation consistent between the complexity statement and the discretization analysis.
[Numerical experiments] The numerical section should report the precise grid sizes and observed runtimes that support the O(τ^{-2-ε}) claim so that the complexity improvement can be reproduced.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed report. The comments highlight important points for strengthening the theoretical sections, and we will revise the manuscript accordingly.

read point-by-point responses

Referee: [Convergence theorem / proof of DP convergence] The central convergence claim (piecewise-linear DP solutions converge under the stated power-law relation between vertical and horizontal steps) is load-bearing. The manuscript must supply the explicit error estimate showing that the faster decay of the vertical step controls the total approximation error; without this quantitative bound the power-law condition remains an assertion rather than a verified sufficient condition.

Authors: We agree that an explicit quantitative error bound is required to rigorously establish the power-law relation as a sufficient condition. The manuscript provides a convergence statement and proof outline under this relation, but we will add a detailed error analysis in the revision that quantifies how the faster decay of the vertical step controls the total approximation error between the DP solutions and the continuous optimum. revision: yes
Referee: [Existence section / admissible set definition] The regularity hypotheses placed on the cost functional and terrain (needed for Arzelà–Ascoli compactness) are not stated explicitly. These hypotheses must be listed and verified to be compatible with the admissible set before the existence result can be accepted as supporting the subsequent numerical scheme.

Authors: We acknowledge that the regularity hypotheses should be stated explicitly. In the revised manuscript we will add a dedicated paragraph listing the required assumptions (continuity and suitable growth conditions on the integrand together with Lipschitz continuity of the terrain elevation) and verify that they are compatible with the admissible set, thereby justifying compactness via Arzelà–Ascoli. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity detected

full rationale

The paper's derivation relies on the Arzelà–Ascoli theorem for existence of a global minimizer in the admissible set (a standard compactness result from analysis) and constructs a dynamic programming scheme whose convergence is proved by controlling approximation errors under an explicit power-law relation between vertical and horizontal discretization steps. This error-control argument is drawn from numerical analysis techniques and does not reduce the claimed convergence to a fitted parameter, self-definition, or prior result by the same authors. The local-search modification yielding O(τ^{-2-ε}) complexity is presented as an algorithmic enhancement with a stated bound, and numerical validation is external to the formal claims. No load-bearing self-citations, smuggled ansatzes, or renamings of known results appear in the chain; the central results remain independent of the paper's own inputs.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The central claims rest on the Arzelà–Ascoli theorem for existence and standard properties of dynamic programming on grids; no free parameters or invented entities are introduced in the abstract.

assumptions (2)

domain assumption The integral cost functional and terrain elevation satisfy conditions for the Arzelà–Ascoli theorem to guarantee a global minimizer exists.
Invoked to establish existence of the optimal trajectory before discretization.
ad hoc to paper The power-law relation between vertical and horizontal discretization steps controls the approximation error sufficiently for convergence of the piecewise-linear DP solutions.
This is the key technical condition stated for the convergence proof.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimal 3D Road Alignment on Topographic Surfaces: A Convergent Dynamic Programming Approach." pith.science (2026). https://pith.science/paper/2503.10922

@misc{pith2026250310922,
  author       = {Pith},
  title        = {Pith review of: Optimal 3D Road Alignment on Topographic Surfaces: A Convergent Dynamic Programming Approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2503.10922}},
  note         = {Machine review of arXiv:2503.10922}
}

read the original abstract

We consider the problem of finding an optimal 3D road trajectory between two points on a terrain with variable elevation. Unlike common heuristic pathfinding methods, we propose a rigorous framework based on the calculus of variations, introducing an integral cost functional that incorporates material delivery and construction expenses. The existence of a global minimizer is established via the Arzel\`a--Ascoli theorem. To solve the problem numerically, we develop a dynamic programming scheme and provide a formal convergence proof. We prove that the sequence of piecewise-linear solutions converges to the true optimum when the grid discretization steps follow a specific power-law relation -- specifically, when the vertical step size decays faster than the horizontal one. To enhance efficiency, we introduce a local-search modification that reduces computational complexity to nearly quadratic O({\tau}^{-2-{\epsilon}}), where {\tau} is the discretization step along the x-axis. Numerical experiments on 2D and 3D terrains validate the theoretical results, showing that our approach achieves accuracy comparable to the Ritz method while significantly reducing processing time.

Figures

Figures reproduced from arXiv: 2503.10922 by the authors.

**Figure 2.** An illustration of the algorithm for finding a local solution. Cir [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗

**Figure 3.** A graph of the optimal solution in Example 1 [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: A graph of the optimal solution in Example 2 [PITH_FULL_IMAGE:figures/full_fig_p021_4.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

[1]

Vestnik S.-Petersburg Univ

Abbasov, M.E., Sharlay, A.S.: Searching for the cost-optimal roa d trajectory on the relief of the terrain. Vestnik S.-Petersburg Univ. Ser. 10. Prik l. Mat. Inform. Prots. Upr. 17(1), 4–12 (2021)

work page 2021
[2]

Math Models Comput Simul

Abbasov, M.E., Sharlay, A.S.: Variational approach for ﬁnding the cost-optimal trajectory. Math Models Comput Simul. 16, 293–301 (2024)

work page 2024
[3]

Bellman R.: Dynamic Programming, Princeton University Press (195 7)

work page
[4]

In: Kaminka, G.A., Lima, P.U., Rojas, R

Bruce J., Veloso M.: Real-time randomized path planning for robot n avigation. In: Kaminka, G.A., Lima, P.U., Rojas, R. (eds) RoboCup 2002: Robot S occer World Cup VI. RoboCup 2002. Lecture Notes in Computer Science, v ol. 2752, pp. 288–295. Springer, Berlin, Heidelberg (2003)

work page 2002
[5]

et al.: Global planning on the mars exploration rovers: software integration and surface testing

Carsten J., Rankin A. et al.: Global planning on the mars exploration rovers: software integration and surface testing. Journal of Field Robot ics 26(4), 337–357 (2009)

work page 2009
[6]

et al.: Convex optimization and A-star algorithm co mbined path planning and obstacle avoidance algorithm

Chen G .R., Guo S. et al.: Convex optimization and A-star algorithm co mbined path planning and obstacle avoidance algorithm. Control and Decisio n 35, 2907– 2914 (2020)

work page 2020
[7]

Robotics and Autonomous Systems 59(5), 329–342 (2011)

Dakulovic M., Petrovic I.: Two-way D* algorithm for path planning an d replan- ning. Robotics and Autonomous Systems 59(5), 329–342 (2011)

work page 2011
[8]

H.: Least cost path in GIS using an accumulated cost su rface and slope lines

Douglas D. H.: Least cost path in GIS using an accumulated cost su rface and slope lines. Cartographica 31, 37–51 (1994)

work page 1994

Show all 30 references

[9]

In: Gass, S.I., Harris, C .M

Gass S.I., Harris C.M.: Dijkstra’s algorithm. In: Gass, S.I., Harris, C .M. (eds): Encyclopedia of Operations Research and Management Science. Sp ringer, New York (2001)

2001
[10]

et al.: Trends and challenges in infrastructu re investment in low-income developing countries

Gurara D., Klyuev V. et al.: Trends and challenges in infrastructu re investment in low-income developing countries. IMF Working Papers 17/233 (201 7) 22
[11]

et al.: Robot path planning using improved rapid ly- exploring random tree algorithm

He D.-Q., Wang H.-B. et al.: Robot path planning using improved rapid ly- exploring random tree algorithm. IEEE Industrial Cyber-Physical Systems (ICPS), 181–186 (2018)

2018
[12]

IEEE Trans

Jaillet L., Cortes J., Simeon T.: Sampling-based path planning on cos tmaps conﬁguration-space. IEEE Trans. Robot. 26(4), 635–646 (201 0)
[13]

Kim, T.Y.; Park, H.S.: Eﬀective analysis framework for construct ion post evalu- ation. J. Korean Soc. Civ. Eng. 36, 1145–1152 (2016)

2016
[14]

M.: Rapidly-exploring random trees: a new tool for pat h planning

LaValle S. M.: Rapidly-exploring random trees: a new tool for pat h planning. The Annual Research Report (1998)

1998
[15]

M., Kuﬀner J

LaValle S. M., Kuﬀner J. J.: RRT-connect: an eﬃcient approach t o single-query path planning. IEEE International Conference on Robotics and Au tomation. Sym- posia Proceedings 2, 995–1001 (2000)

2000
[16]

et al.: PQ-RRT*: an improved path planning algorithm f or mobile robots

Li Y., Wei W. et al.: PQ-RRT*: an improved path planning algorithm f or mobile robots. Expert Syst Appl. 152:113425 (2020)

2020
[17]

Joh n Wiley & Sons Inc (1975)

Lusternik L.A., Sobolev V.J.: Elements of Functional Analysis. Joh n Wiley & Sons Inc (1975)

1975
[18]

N.: Numerical Methods in the Theory of Optimal Syste ms

Moiseev N. N.: Numerical Methods in the Theory of Optimal Syste ms. Moscow, Nauka (1971)

1971
[19]

et al.: Terrain based D* algorithm for path planning

Saranya C., Unnikrishnan M. et al.: Terrain based D* algorithm for path planning. IF AC-PapersOnLine 49(1), 178–182 (2016)

2016
[20]

Sniedovich, M.: Dynamic Programming: Foundations and Principles , Taylor & Francis (2010)

2010
[21]

Indian J

Sudhakara P., Ganapathy V.: Trajectory planning of a mobile rob ot using en- hanced A-star algorithm. Indian J. Sci. Technol. 9(41), 1–10 (201 6) 23
[22]

Inte rnational Journal of Geographical Information Science

Tomlin D.: Propagating radial waves of travel cost in a grid. Inte rnational Journal of Geographical Information Science. 24(9), 1391–1413 (2010)

2010
[23]

et al.: A learning-based multi-RRT approach for ro bot path planning in narrow passages

Wang W., Zuo L. et al.: A learning-based multi-RRT approach for ro bot path planning in narrow passages. J Intell Robot Syst. 90(1), 81–100 ( 2018)

2018
[24]

Habitat Int

Won, S., Cho, S.E., Kim, S.: The neighborhood eﬀects of new road in frastructure: Transformation of urban settlements and resident’s socioeconom ic characteristics in Danang, Vietnam. Habitat Int. 50, 169–179 (2015)

2015
[25]

Wu, C.H.; Hsieh, T.Y.; Cheng, W.L.: Statistical analysis of causes fo r design change in highway construction on Taiwan. Int. J. Proj. Manag. 23 , 554–563 (2005)

2005
[26]

et al.: Application improvement of A* algorithm in intellig ent vehicle trajectory planning

Xiong X., Min H. et al.: Application improvement of A* algorithm in intellig ent vehicle trajectory planning. Math Biosci Eng MBE 18(1), 1–21 (202 1)
[27]

Yu C., Lee J. et. al.: Extensions to least-cost path algorithms fo r roadway plan- ning. International Journal of Geographical Information Scienc e 17(4), 361–376 (2003)

2003
[28]

Yuan Yi J., Sun Q. R. et al. Path planning of a manipulator based on an improved P RRT* algorithm. Complex Intell. Syst. 8, 2227–2245 (2022)

2022
[29]

F., Fugenschuh A

Zazai M. F., Fugenschuh A. R.: Computing the trajectories for the development of optimal routes. Optimization and Engineering 22, 975–999 (2021 )

2021
[30]

, Golab A

Zwickl-Bernhard S. , Golab A. et al.: Designing a model for the cos t-optimal decommissioning and refurbishment investment decision for gas net works: Appli- cation on a real test bed in Austria until 2050. Energy Strategy Re views 49:101138 (2023) 24

Pith tools

Reviewed May 22, 2026 · model on record in the stance chip above.

[1] [1]

Vestnik S.-Petersburg Univ

Abbasov, M.E., Sharlay, A.S.: Searching for the cost-optimal roa d trajectory on the relief of the terrain. Vestnik S.-Petersburg Univ. Ser. 10. Prik l. Mat. Inform. Prots. Upr. 17(1), 4–12 (2021)

work page 2021

[2] [2]

Math Models Comput Simul

Abbasov, M.E., Sharlay, A.S.: Variational approach for ﬁnding the cost-optimal trajectory. Math Models Comput Simul. 16, 293–301 (2024)

work page 2024

[3] [3]

Bellman R.: Dynamic Programming, Princeton University Press (195 7)

work page

[4] [4]

In: Kaminka, G.A., Lima, P.U., Rojas, R

Bruce J., Veloso M.: Real-time randomized path planning for robot n avigation. In: Kaminka, G.A., Lima, P.U., Rojas, R. (eds) RoboCup 2002: Robot S occer World Cup VI. RoboCup 2002. Lecture Notes in Computer Science, v ol. 2752, pp. 288–295. Springer, Berlin, Heidelberg (2003)

work page 2002

[5] [5]

et al.: Global planning on the mars exploration rovers: software integration and surface testing

Carsten J., Rankin A. et al.: Global planning on the mars exploration rovers: software integration and surface testing. Journal of Field Robot ics 26(4), 337–357 (2009)

work page 2009

[6] [6]

et al.: Convex optimization and A-star algorithm co mbined path planning and obstacle avoidance algorithm

Chen G .R., Guo S. et al.: Convex optimization and A-star algorithm co mbined path planning and obstacle avoidance algorithm. Control and Decisio n 35, 2907– 2914 (2020)

work page 2020

[7] [7]

Robotics and Autonomous Systems 59(5), 329–342 (2011)

Dakulovic M., Petrovic I.: Two-way D* algorithm for path planning an d replan- ning. Robotics and Autonomous Systems 59(5), 329–342 (2011)

work page 2011

[8] [8]

H.: Least cost path in GIS using an accumulated cost su rface and slope lines

Douglas D. H.: Least cost path in GIS using an accumulated cost su rface and slope lines. Cartographica 31, 37–51 (1994)

work page 1994