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

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à --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(τ^{-2-ε}), where τ 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.

This is the peer-reviewed version of the article, accepted for publication in New Zealand Journal of Mathematics (to appear)