A Primal-Dual Level Set Method for Computing Geodesic Distances
Hailiang Liu, Laura Zinnel · 2026
Read A Primal-Dual Level Set Method for Computing Geodesic Distances by Hailiang Liu, Laura Zinnel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-23244.txt.
Introduction
Hailiang Liu and Laura Zinnel compute geodesic distances, the shortest paths across curved surfaces. Such distances underpin shape analysis, graphics, and navigation on surfaces. Surface geometry bends shortest paths, making them harder than flat Euclidean distances.
Their primal-dual level set method computes both paths and distances in a unified scheme. Level set methods track fronts through a surface, which suits distance propagation. Reliable geodesic tools support medical imaging, computer vision, and mesh processing. Surface geometry bends the shortest paths, so the method must respect curvature rather than flattening the surface first. The primal-dual level set formulation is the paper's contribution to this long-standing computational geometry task.
Catalog record
| CREATOR | Hailiang Liu, Laura Zinnel |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-23244
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Primal-Dual Level Set Method for Computing Geodesic Distances Thanks: This work by Zinnel is partially supported by the National Science Foundation Grant DGE-2152117. Hailiang Liu, Laura Zinnel Abstract . The numerical computation of shortest paths or geodesics on surfaces, along with the associated geodesic distance, has a wide range of applications. Compared to Euclidean distance computation, these tasks are more complex due to the influence of surface geometry on the behavior of shortest paths. This paper introduces a primal-dual level set method for computing geodesic distances. A key insight is that the underlying surface can be implicitly represented as a zero level set, allowing us to formulate a constraint minimization problem. We employ the primal-dual methodology, along with regularization and acceleration techniques, to develop our algorithm. This approach is robust, efficient, and easy to implement. We establish a convergence result for the high-resolution PDE system, and numerical evidence suggests that the method converges to a geodesic in the limit of refinement. 1991 Mathematics Subject Classification 90C46, 93B40 1. Introduction A geodesic is a curve on a surface that minimizes local length, serving as a useful generalization of straight lines in Euclidean space. Geodesic distances play a crucial role in both theoretical and applied problems, including those in computer vision [ 10 ] , conformal field theory [ 18 ] , quantum field theory [ 7 ] , and geophysical visualization [ 13 ] . Therefore, approximating the minimal geodesic path between two points on a surface is essential in many application domains. The approximation tasks can be framed as constrained optimization problems; however, they are often highly non-convex, and effective algorithms for computing geodesic distances are limited. For complex surfaces represented in 3D meshes, specialized algorithms such as the fast-marching method [ 19 ] , the Dijkstra algorithm ( [ 13 , 21 , 20 ] ), or the heat flow method [ 11 ] are often employed to find the shortest path across the surface. Although effective, these methods often involve considerable complexity due to the construction of a mesh or graph representation. In contrast, our algorithm approximates geodesics on surfaces without requiring any surface discretization. In this work, we adopt a different strategy: using the level set of a function to represent the surface, rather than employing a triangulated mesh. In the literature, methods based on implicit level set surfaces are referred to as level set methods, which are particularly effective in image science applications, including image segmentation and rendering [ 23 ] . In this work, we introduce a primal-dual method for approximating geodesic distances and minimal geodesic paths on surfaces represented by level set functions. 1.1. Background In differential geometry [ 1 ] , the tangent space to a surface \Omega at a point p , is defined by T_{p}\Omega=\{\dot{\xi}(0)~|~\xi:(-\varepsilon,\varepsilon)\to\Omega\text{ is }C^{\infty}\text{ and }\xi(0)=p\}. A surface is considered orientable if there exists a continuous function N on \Omega such that for each p , the vector N(p) is orthogonal to T_{p}\Omega . This field of normal vectors N is referred to as an orientation of \Omega . Notably, if \Omega is the zero level set of function \phi:\mathbb{R}^{3}\to\mathbb{R} , and \gamma:[0,1]\to\Omega is a path on \Omega , then \phi(\gamma(t))=0\Rightarrow\nabla\phi(\gamma(t))\cdot\dot{\gamma}(t)=0\quad\text{for}\quad t\in[0,1]. Thus, \dot{\gamma}(t)\in T_{p}(\Omega) . If the surface is smooth and the vector field is defined as N(p):=\frac{1}{|\nabla\phi(p)|}\nabla\phi(p) for every point p=\gamma(t) along the curve, then N provides an orientation of \Omega . A curve \gamma:[0,1]\to\Omega is a geodesic if and only if \ddot{\gamma} is orthogonal to the tangent plane of \Omega at \gamma(t) for all t\in[0,1] [ 25 ] . Further, for a zero level set surface \Omega with orientation N as defined above, if \ddot{\gamma} is parallel to N(p) for every point p=\gamma(t) along the curve, then \gamma is a geodesic. It is known that if \gamma is a shortest path, then \gamma is a geodesic; however, not every geodesic represents a shortest path [ 25 , 10 ] . For example, if p and q are points on a sphere, then there is both a long and a short great circle arc joining these points. Both of these great circle arcs are geodesics, but the short great circle arc is the shortest geodesic [ 25 ] . The fact that not all geodesics are shortest paths, along with the fact that a shortest geodesic between two points is not necessarily unique, complicates the task of finding a minimal geodesic on a surface. 1.2. Problem Setup Our goal is to develop an efficient algorithm for iteratively computing a geodesic and the geodesic distance (shortest path) between two points on a surface. Let \Omega be a surface represented as the zero level set \{x\in\mathbb{R}^{3}~|~\phi(x)=0\} of a function \phi:\mathbb{R}^{3}\to\mathbb{R} . For p,q\in\Omega and a path \gamma:[0,1]\to\mathbb{R}^{3} with \gamma(0)=p and \gamma(1)=q , the length of \gamma is calculated by \int_{0}^{1}|\dot{\gamma}(t)|~dt. We are particularly interested in paths from p to q on \Omega . That is, we seek path \gamma to be in the set \Gamma(p,q,\Omega) defined by \Gamma(p,q,\Omega)=\left\{\gamma~:~\gamma(0)=p,\gamma(1)=q,\text{ and }\phi(\gamma(t))=0~\forall t\in[0,1]\right\}. Recall that a path \gamma:[0,1]\to\mathbb{R}^{3} is a geodesic if \gamma\in\Gamma(p,q,\Omega) and \ddot{\gamma} is orthogonal to the tangent plane of \Omega at \gamma(t) for all t\in[0,1] . Hence, (1.1) \ddot{\gamma}\cdot\dot{\gamma}=0. It has been shown that the shortest length path between any two points on a surface must be a geodesic [ 25 ] . The geodesic distance from p to q is the length of the shortest length path \gamma from p to q on the surface \Omega . That is, the length of path \gamma such that (1.2) \gamma=\argmin_{\xi\in\Gamma(p,q,\Omega)}\int_{0}^{1}|\dot{\xi}(t)|~dt. Using this formulation, we propose determining the geodesic distance by solving the following optimization problem: \displaystyle\min_{\gamma\in\Gamma(p,q,\Omega)}\frac{1}{2}\int_{0}^{1}|\dot{\gamma}(t)|^{2}~dt, which can be shown to be equivalent to ( 1.2 ). To eliminate the level set constraint, a Lagrangian multiplier \lambda(t)\in C^{1}[0,1] is introduced in an inf-sup problem: \inf_{\gamma}\sup_{\lambda}\left\{\frac{1}{2}\int_{0}^{1}|\dot{\gamma}(t)|^{2}~dt+\int_{0}^{1}\lambda(t)\phi(\gamma(t))~dt\right\}. A simple strategy is to alternate a gradient-like descent in \gamma and a gradient-like ascent in \lambda . This yields the following iterative scheme: \begin{cases}\lambda_{k+1}(t)=\lambda_{k}(t)+\tau_{\gamma}\phi(\gamma_{k}(t)),\\ \gamma_{k+1}(t)=\gamma_{k}(t)-\tau_{\lambda}\left(-\ddot{\gamma}_{k}(t)+\lambda_{k+1}(t)\nabla\phi(\gamma_{k}(t))\right),\end{cases} where \tau_{\gamma},\tau_{\lambda} are tunable step sizes. However, such basic updates may not perform well in all cases due to stability issues inherent in the formulation. To address this, we augment the functional with a regularization term of the form: \mathcal{L}_{\varepsilon}[\gamma,\lambda]=\frac{1}{2}\int_{0}^{1}|\dot{\gamma}|^{2}~dt+\int_{0}^{1}\lambda(t)\phi(\gamma(t))dt-\frac{\varepsilon}{2}\int_{0}^{1}\lambda^{2}(t)~dt and enhance the gradient descent-ascent updates with a relaxation step, resulting in the following update scheme: \begin{cases}\lambda_{k+1}(t)=\frac{1}{1+\varepsilon\tau_{\lambda}}(\lambda_{k}(t)+\tau_{\lambda}\phi(\gamma_{k}(t))),\\ \tilde{\lambda}_{k+1}(t)=\lambda_{k+1}(t)+\omega(\lambda_{k+1}(t)-\lambda_{k}(t)),\\ \gamma_{k+1}(t)=\gamma_{k}(t)-\tau_{\gamma}(-\ddot{\gamma}_{k}(t)+\tilde{\lambda}_{k+1}(t)\nabla\phi(\gamma_{k}(t))),\end{cases} where \varepsilon>0 is a regularization parameter, \omega\in[0,1] controls the degree of relaxation, and \tau_{\lambda},\tau_{\gamma} are tunable step sizes. This refinement has been shown to significantly improve stability and numerical performance. Notably, the use of relaxation in this manner has also been explored in the Primal-Dual Hybrid Gradient (PDHG) method [ 6 , 15 ] which addresses saddle-point problems of the primal-dual form: \min_{y\in Y}\max_{x\in X}g(x)+\left(\langle Ax,y\rangle-f^{*}(y)\right). PDHG has proven to be an efficient algorithm for a wide range of problems, particularly in imaging applications, and has gained popularity due to its strong convergence guarantees. For further details, readers are referred to [ 6 ] , specifically Section 2.5 for a brief description. Our problem setup, which employs a novel level set representation, has not been previously explored. This approach establishes a primal-dual connection between the curve \gamma and the multiplier \lambda , resulting in an algorithm with