DEEP ACCURATE SOLVER FOR THE GEODESIC PROBLEM
Authors: Saar Huberman
Ron Kimmel
Venue: Submitted to ICLR 2023 (2023)
Keywords: Geodesic distance
Geometric Deep learning.

Abstract: A high order accurate deep learning method for computing geodesic distances on surfaces is introduced. The proposed method exploits a dynamic programming principle which lends itself to a scheme with quasi-linear computational complexity. We consider two main components for computing distances on surfaces; A numerical solver that locally approximates the distance function and an efficient causal ordering scheme by which points are updated. The quality of the distance approximation is determined by the local solver and is the main focus of this paper. A common approach to compute distances on continuous surfaces is by considering a discretized polygonal mesh approximating the surface, and estimating distances on the polygon. With such an approximation, the exact geodesic distances restricted to the polygon are at most second order accurate with respect to the distances on the corresponding continuous surface. Here, by order of accuracy we refer to the rate of convergence as a function of the average distance between sampled points. To improve the rate of convergence, we consider a neural network based local solver which implicitly approximates the structure of the continuous surface. The proposed solver circumvents the polyhedral representation, by directly consuming sampled mesh vertices for approximation of distances on the sampled continuous surfaces. We provide numerical evidence that the proposed update scheme, with appropriate local numerical support, provides better accuracy compared to the best possible polyhedral approximations and previous learning based methods. We introduce a trained solver which is third order accurate, with quasi-linear complexity in the number of sampled points.

Under review as a conference paper at ICLR 2023
DEEP ACCURATE SOLVER FOR THE GEODESIC PROBLEM
Anonymous authors Paper under double-blind review
ABSTRACT
A high order accurate deep learning method for computing geodesic distances on surfaces is introduced. We consider two main components for computing dis- tances on surfaces; A numerical solver that locally approximates the distance func- tion and an efficient causal ordering scheme by which surface points are updated, The proposed method exploits a dynamic programming principle which lends it- self to a scheme with quasi-linear computational complexity. The quality of the distance approximation is determined by the local solver and is the main focus this paper. A common approach to compute distances continuous surfaces is by considering a discretized polygonal mesh approximating the surface, and esti- mating distances the polygon. With such approximation, the exact geodesic distances restricted to the polygon are at most second order accurate with respect the distances on the corresponding continuous surface. Here, by order ac- curacy we refer to the rate of convergence as a function of the average distance between sampled points. To improve the accuracy, we consider a neural network based local solver which implicitly approximates the structure of the continuous surface. The proposed solver circumvents the polyhedral representation, by di- rectly consuming sampled mesh vertices for approximation of distances on the sampled continuous surfaces. We supply numerical evidence that the proposed learned update scheme, with appropriate local numerical support, provides better accuracy compared to the best possible polyhedral approximations and previous learning based methods. We introduce trained solver which is third order accu- rate, with quasi-linear complexity in the number of sampled points.
INTRODUCTION
Geodesic distance defined as the length of the shortest path connecting two points on a surface. can be considered as generalization of the Euclidean distance to curved manifolds. The approx- imation of geodesic distances is used as a building block in many applications. It can be found in robot navigation (Kimmel al. 1998, Kimmel & Sethian 2001). and shape matching (Ion et al., 2008 Elad & Kimmel [001]] Shaamai & Kimmel| 2017] Panozzo et al.) (2013). to name just a few examples. Thus, for effective and reliable use, computation of geodesics is expected to be both fast and accurate.
Over the years, many methods have been proposed for computing distances polygonal meshes that compromise between the accuracy of the distance approximation and the complexity of the algorithm. One family of algorithms for computing distances in this domain is based on solutions to the exact discrete geodesic problem introduced by Mitchell et al. 1987). This problem is defined as that of finding the exact distances on a polyhedral mesh. The algorithms introduced so far for solving the discrete geodesic problem involve substantially higher than linear complexity which makes them impractical for operating on surfaces sampled by a large number of vertices. At the other end, popular family of methods for efficient approximation of distances known as fast marching, involves quasi-linear computational complexity. These methods are based on the solution of the eikonal equation and consists of two main components, a heap sorting strategy and a local causal numerical solver, often referred to as a numerical update procedure. Fast marching, originally introduced for extended to triangulated surfaces in Kimmel & Sethian (1998). While operating on curved surfaces approximated by triangulated mesh the first proximity neighbors of vertex in the mesh are used to locally approximate the solution of
regularly sampled grids (Sethian 1996] Tsitsiklis 1995),

---

Under review as a conference paper at ICLR 2023
eikonal equation, resulting in fiirst-order--cccraat scheme in terms of a typical triangle's edge length denoted as h.
It can be easily shown that the exact geodesic distances computed on a polygonal mesh approximating a continuous surface would be most second order approximation of the corresponding dis- tances on the surface (see Appendix (A.I). D. To overcome the second order limitation, we extend the numerical support about each vertex beyond the classical one ring approximation, and utilize the uni- versal approximation properties of neural networks. We develop a neural network based local solver that overcomes the second order approximation limitation induced by geodesics restricted poly- hedral meshes. We exploit the low complexity of the well-known dynamic programming update scheme (Dijkstra 1959), and com- bine it with a novel neural network-based solver, resulting in an efficient and accurate method.
In related effort (Lichtenstein et al. 2019), neural network based local solver for the computation geodesic distances was pro- posed. We improve upon Lichtenstein's O(h2) approach by tending the local neighborhood numerical support, and refining the network's architecture to obtain O(h)) accuracy at similar linear complexity.
The proposed local solver is trained in supervised manner using ground truth examples. Since geodesics can not be derived analyti- cally except for limited set of surfaces like spheres and planes, we propose a multi-hierarchh ground truth generation technique. The suggested framework uses distance approximations on high resolu- tion sampled meshes to better approximate distances on lower reso- lution meshes. We thereby utilize our ability compute high order solvers generate accurate training examples at low resolution.
Figure 1: Geodesic distance from single source point on a surface. Our method produces highty accurate dis- tance maps while operating in quasi-linear time.
1.1 CONTRIBUTIONS
We develop a fast and accurate geodesic distance approximation method on surfaces.
For fast computation, we use a distance update scheme (Algorithm) T that guarantees quasi- linear computational complexity.
For accurate approximation, develop neural network based local solver with wide
local neighborhood support that operates directly on the sampled mesh vertices.
To provide accurate ground truth distances required for training our solver, we propose novel data generation bootstrapping procedure.
RELATED EFFORTS
Given a domain Ω Ra and curve T Ω the predominant approach for generating distance functions from the curve to all other points in Ω is to find function Φ : Ω - which satisfies the eikonal equation,
[o(()) ((x) = 0, FET.
ZERir
(1)
Due to the non-linearity and hyperbolicity of this partial differential equation (PDE), solving directly is challenge. Common solvers sample the continuous domain and approximate the solution on the corresponding discretized domain while being consistent with viscosity solutions.
Fast Eikonal Solvers. Sethiaa (1996); Tsitsiklis (1995), -insi algorithms for approximat- ing distances on regularly sampled grids were introduced. These algorithms involve ONN log(N)) complexity, where N is the number of points the grid. For example, the fast marching algorithm
2

---

Under review as a conference paper at ICLR 2023
consists of two main parts, numerical solver that locally estimates the distance function, by approx- imating a solution of an eikonal equation, and an ordering scheme that determines which points are visited at each iteration. Over the years, more sophisticated local solvers have been developed which utilize wide local support and lead to second (Sethian) 1999) and third (Ahmed et al. 2011) order accurate methods. Kimmel & Sethian (1998) extended the fast-marching scheme to approximate first-order accurate geodesic distances on triangulated surfaces. Another prominent class of numer- ical solvers the fast sweeping methods (Kimmel & Mauuer 2006 Zhao 2005 Li et al. 2008
Weber et al., 2008), iterative schemes that use alternating sweeping ordering. These methods have an asymptotic complexity of O thus, they are usually considerably slower since they require many sweeps to converge to accurate results in worst case scenarios (Hysing & Turek 2005).
Geodesics in Heat. Instead of directly solving the hyperbolic eikonal equation, the heat method pre- sented in Crane et al. (2013) solves a linear elliptic PDE for heat transport. The suggested approach requires the solution of a diffusion equation and Poisson equation. An advantage promoted that paper, is that the required linear systems can be pre-factored per mesh, which leads to computational efficiency when calculating distance maps from multiple sources. It has been empirically shown that the heat method leads to first order approximation of geodesic distances on average. The distance functions produced with the heat method are smoother than those generated with fast marching and less accurate near the discontinuities of the distance functions.
Window Propagation Methods. Trying to solve the discrete geodesic problem, Mitchell et al. 1987) proposed ONN2log(N)) complexity algorithm known as MMP. This algorithm was the first method introduced for computing exact distances on non-convex triangulated surfaces. In its original formulation, it calculates the distance from a single source to all other points on the polygonal mesh. The main idea of this algorithm is to track groups of shortest paths that can be atomically parameterized. This is achieved by dividing each mesh edge into a set of intervals, which are referred to as windows. This quadratic algorithm is computationally demanding and challenging to code. In fact, the first implementation was introduced (2005). Over the years, many improvements to the exact geodesic scheme were suggested (Xu et al., 2015 Ying et al. 2014 Trettner et al. (202I). p. For example, the Vertex-oriented Triangle Propagation (VTP) algorithm (Qin et al. 2016), which by sorting out superfluous windows is considered to be one of the fastest exact geodesics algorithms on polyhedral surfaces.
years after its publication, by [Surazhsky et al.
Deep Learning Based Methods. A number of recent papers exploited neural networks approxima-
tion capabilities to numerically solve PDEs (Greenfeld et al.] 2019 Hsich et al.) 2019) bin Waheed al., (021). Similar our strategy, Lichtenstein et al. (2019) proposed deep learning based method for geodesic distance approximation. It uses a heap sort ordering scheme while introducing neural network based local solver. For each distance evaluation of a target point p, local neigh- borhood is obtained as input to the solver. This neighborhood consists of all vertices connected to p by a path with most 2 edges, which we refer to second-ring -oonnd-ing neighborhood. The proposed method showed second-order accuracy, similar to the exact geodesic method (Mitchell et al. 1987), while operating at quasi-linear (N log(N)) computational complexity.
Curve Shortening Methods. A geodesic is defined as the path connecting two points on a surface, which characterized by having zero geodesic curvature at each point along the curve. Between two points on a surface, there can be multiple geodesic paths with different corresponding distances. The geodesic distance is defined as the length of the minimal geodesic connecting each point on the surface to some source points at which the distance is defined to be zero A geodesic path can be extracted by starting with an arbitrary path on the surface and applying a length shortening method. Kimmel & Sapiro (1955) presented curve shortening flow that fixes the two endpoints of the curve at each iteration and minimize the geodesic curvature. SSharp & Crane (2020) presented curve shortening method for triangulated meshes by considering paths constrained to the mesh edges and applying intrinsic edge flips. These local refinement methods converge an initial guess into a geodesic which is not necessarily the minimal one.
3 GEODESIC DISTANCES: O(h3) ACCURATE AT QUASI-LINEAR COMPLEXITY
We present neural network based method for approximating accurate geodesic distances sur- faces. Similar to most dynamic programming methods, like the fast marching scheme, the proposed method consists of numerical solver that locally approximates the distance function u, and an
3

---

Under review as a conference paper at ICLR 2023
dering scheme that defines the order of the visited points. Here, the points divided into three disjoint sets.
1. Visited: points where the distance function u(p) has already been computed and will not be changed.
2. Wavefront: points where the computation of u(p) is in progress and is not yet fixed.
3. Unvisited: points where u() has not yet been computed.
Algorithm Distance Updating Scheme
1: Definitions:
S Set of all source points
p point on the surface
u(p) minimal distance from sources to p
2: Initialize:
u(p) 0, tag p as Visited; Vp
u(p) = oc, tag as Unvisited; Yp & S
Tag all Unvisited points adjacent to Visited points as Wavefront
3: repeat
4: for E Wavefront do
5: Approximate u(p) based on Visited points
6: Tag p as Wavefront
7:
end for
8:
Tag the least distant Wavefront point as Visited
9: Tag all Unvisited neighbors of p' as Wavefront
until all points are Visited.
11:
Return
The distances at the sampled surface points are computed according to Algorithm where Step of the scheme is performed by the proposed local solver. When applied to target point p Wave- front, the local solver uses predefined maximum number of Vivited points. These Visited points are chosen from the local neighborhood and are not related to the number of points on the mesh; hence, single operation of our solver has constant complexity. Since, within our dynamic program- ming setting, the proposed method retains the heap sort ordering scheme, the overall computational complexity is O(N log(N)).
Section introduces the operation the local solver, presents the required pre-processing and elaborates the implementation of the neural network. Section 3.2 explains how the dataset is generated and the network weights are optimized. Section 3.3 3.3 details how ground truth distances are calculated when analytic closed form is available.
3.1 LOCAL SOLVER
We present an application of novel local neural network-based solver. It can be used distance approximation method in Step 5 of Algorithm [ When the solver applied to a given point p E Wavefront, it receives input the coordinates and distance function values of its neighboring points. The neighboring points, denoted by (((p) = {P1, P2..... PM J. are defined by all vertices connected p by path of most edges, which is often referred to third ring neighborhood. Based on the information from the Visited points in N(p), the local solver approximates the distance function u(p). This way, we keep utilizing the order of updates that characterizes the construction of distance functions.
As mentioned earlier, for given target point p and neighboring points ( Visited (p()), the input to our solver is {ITp,) Bp. Zp,, u(p,) JMM U (ZTp Vp. 2.) To address the solver's general- ization capability and to handle diverse possible inputs, we transform the input to the neural network into canonical representation. To this end, design a preprocessing pipeline. The coordinates centered with respect to the target point, resulting in relative coordinates (I,, - -Fpp Up. - Upp Ep. - =p), ( (u(p))) is subtracted from the values of the distance function (u(p))MM 1- After the input and min;
is centered, it is scaled that the mean 1.2 norm of the coordinates is of unit size. Last, S0(3)
4

---

Under review as a conference paper at ICLR 2023
U1
MLP
Max Pooling
U2
MLP
Linear, LeakyReLU (512,1004,512,,56,.)
u(p)
UM
MLP
1, = (It, Ukr 2e, u(p:))
MLP
Point Residual (Pres) Block
Lineer LeakyReLU
Liner,, Leary (128,256)
Lakky Rel.1
LeakyRet..
(4,133)
(135, 128)
Prox
(128,128
Pros (256,360)
Prox (2562560)
Liner (256.3
Limer
Figure 2: The proposed network architecture described in Section 3.1 The input coordinates and distance function are in their canonical form, after translation rotation and scale.
rotation matrix is applied to the coordinates so that their first moment is aligned with a predefined direction. The processed input is fed into the neural network and the output further processed to reverse the centering and scaling transformations.
Our input neighborhood has no fixed order and can be viewed as set. properly handle our unstructured set of points, we prefer our neural network output to be permutation invariant. Our architecture, shown schematically Figure 2 is based on the Pointnet model (Qi et al., 2017) and consists of three main components. (1) A shared weight encoder that lifts the 4-dimensional input to 512 features using residual multi-layer perceptron (MLP) blocks (Ma et al. 2022). (2) a per-feature max pooling operation that results in single 512 feature vector, and (3) fully connected regression network of dimensions (512, 1024, 512, 256, 1) that outputs the desired target distance.
3.2 TRAINING THE LOCAL SOLVER
We use a customary supervised training procedure, using examples with corresponding ground-truth distances. These ground truth distances obtained by applying bi-level sampling strategy, de- tailed in Section 3.3 Given an input {(Ip, Pp. Zp., u(p, ), our network is trained to minimize the difference between its output and its corresponding ground truth, denoted by (p). To develop a reliable and robust solver, we create a diverse dataset that simulates a variety of scenarios. We construct this dataset by selecting various source points and sampling local neighborhoods differ- ent random positions relative to the sources. According to the causal nature of our algorithm, we build our training examples, such that a neighboring point is defined Visited and is allowed to participate in the prediction of u(p) if (p') < Ugg (p). The network's 's parameters θ are optimized minimize the Mean Square Error (MSE) loss
K
L(e) = K
Σ j=1
(fe(f(Ipi)) Uou,y Ep,, ul u(p. (p;)))
(2)
where is the number of examples in the training set and Pi, corresponds to the th neighbor of the target point Py- The coordinates and distances used in training procedure are in their canonical form, after being translated, rotated and scaled, as explained in Section 3.1
3.3 LEARNING TO AUGMENT
Exact distances on continuous surfaces are given by analytic expressions for very limited set of continuous surfaces; namely, for spheres and planes. Since solver trained on examples taining ground truth distances, an additional approximation algorithm must be considered to gener- training examples for general surfaces. Currently, the most accurate axiomatic method for
5

---

Under review as a conference paper at ICLR 2023
nd order MMP
Algorithm
Sampled geodesic distance
update
Mash
structure
Figure 3: Bootstrapping by training. Distance values computed for a high h resoluuuuo sampled mesh of a continuous surface with accurate scheme yields O(h²r) accurate distances given at the mesh points. The mesh can then be sampled into lower h-resolution mesh of the same continuous surface, while keeping the corresponding O(h2r) accurate distances at the vertices. See text for an elaborated discussion regarding data augmentation at high resolution and training more accurate update procedures the low resolution.
distance computation is the MMP algorithm, which computes "exact" polyhedral distances. Consid- ering polyhedral surfaces as sampled continuous ones, the "exact" distances on triangulated surfaces are 2nd order accurate with respect to the edge length h. Therefore, the MMP is an O accurate method. In order train our network with more accurate than O(h)) distances for general smooth surfaces, we resort to the following bootstrapping idea.
We introduce multi-resolution ground truth boosting generation technique that allows us obtain ground truth distances of any desired order. The underlying idea is that distances computed on mesh obtained from denser sampling of the surface are a better approximation the distances on the continuous surface.
When generating examples from a given surface, two sampling resolutions the surface are ob- tained and corresponding meshes are formed, denoted by Sdense and Saperse, respectively. Dis- tances are computed on the high-resolution mesh Sdense and the obtained distance map is sampled at S Spparse-
Consider hdense, heporee that correspond to the mean edge length of the polygons Sdense S Saparses so that,
hdense
12 Sparse
The distances computed by an approximation method of order on Saense are order accurate Ohtienee): Therefore, the same approximated distances, sampled at the corresponding vertices of S Saparse have O (hhr (hoparse) accuracy.
Using the distance samples of the polyhedral distances obtained by the MMP algorithm while re- quiring q 2 in Equation (3), allows us to generate distance maps that are least fourth-order accurate. By considering these approximated distances our ground truth, training examples can be generated from Separse as described in Section which allow us to properly train a third-order accurate method. The iterative application of this process allows us to generate accurate ground truth distances to properly train solvers of arbitrary order. For example, after training 3nd order solver, apply the same process while replacing the MMP with our solver to generate (h²) ground truth distances and train a solver up to 6t order. For a schematic representation of this technique, see Figure

---

Under review as a conference paper at ICLR 2023
Li loss
10
Resolution
10
Enror
Resolution
10
Accuracy
FMM 0.88
MMP 1.96
Ours 3.02
0.1
Resolution
(a)
Figure 4: Order of accuracy: (a) Mesh approximations of a unit sphere with different edge resolu- tions. (b) Plots showing the effect of the edge size on the errors. The accuracy of each scheme is associated with corresponding slope.
4 NUMERICAL EVALUATION
4.1 ANALYTICALLY COMPUTED GROUND TRUTH
Geodesic distances spheres be calculated analytically. Therefore, they well suited for the evaluation of our method. For two given points a = (Fa, ya, =a), (Ts, yb. 2b) lying on sphere of radius r, the geodesic distance between them is defined by
To + yalb + 26
u(a, b)
arccos
(4)
22
To train our solver, we first randomly sampled spheres at different resolutions and obtained a trian- gulated version of them. Using the distances calculated by Equation ④ we then created a rich data
and applied training procedure as presented in Section 3.2, To evaluate our method, we create
hierarchy of sphere resolutions as illustrated in Figure 4a
As described in Osher & Sethian (1988), we assume that the exact solution u(a, b) can be written as un (a. O
u(a,
(5)
where is a constant, 4y defined as the approximate solution on a mesh with a corresponding mean edge length of h, and R is the order of accuracy. For two given mesh resolutions of the same continuous surface SJ, S2 with corresponding 11 h2, we can estimate our method's order of accuracy by
u 24/1
R
log
(6)
21/22
The evaluation of our method shown in Figure 4b where the slope of the line indicates the order of accuracy R. It can be seen that our method has higher order of accuracy than the classical fast marching, the exact geodesic method, and the previous deep learning method proposed by Lichten- stein et al.
4.2 GENERALIZATION TO POLYNOMIAL SURFACES
We evaluated our method on second order polynomial surfaces. In general, there is no closed form analytical expression for geodesic distances on these surfaces. To train our solver, we generated wide variety of polynomial surfaces and obtained an accurate approximation of their geodesics for range of sampling resolutions, described in Section 3.3 After obtaining accurate geodesic distance map, we created training set and trained our model according to Section An evaluation of our method on surfaces from this family is shown in Table and Figure

---

Under review as a conference paper at ICLR 2023
Table 1: Polynomial surfaces: Quantitative evaluation conducted on 2nd order polynomial surfaces.
The errors computed relative to the polyhedral distance projected from high-resolution sampled meshes, as described in Section 3.3
Surface
FMM
Lichtenstein et al.
MIP
Ours
FMM
Lichtenstein al.
MMP
Ours
0.02861
0.00213 0.00339 0.00336
0.00094
0.00043
0.0795
0.0117
0.0024
0,0016
0.02053
0.00276
0.00096
0.0680
0.0144
0.0067
0,0026
ay
0.02913
0,00182
0.00088
0.0640
0,0260
0.0063
0,0028
4.3
GENERALIZATION TO ARBITRARY SHAPES
Ours
Exact Polyhedral
To better emphasize the generalization ability of our method, we conduct additional experiment. We train our solver only on the three 2nd order polyno- mial surfaces shown in Table T and evaluate it on arbitrary shapes from the TOSCA dataset (Bronstein al. 2008). It can be seen in Figure [6] that our method generalizes well and leads to significantly lower eπrors compare to the heat method, classical fast marching and the method presented by Lichten- stein et al. 2019) when trained on the same poly- nomial surfaces. Errors are computed relative to the polyhedral distances, since they are the most accu- rate distances available to us for these shapes. For a more detailed analysis of the generalization of our method to Tosca, one can see Table 3 and Figure 9 in the Appendix.
0,000476 0.000951 0.00143 0.00190
Figure 5: Polynomial surfaces: Errors pre- sented for the polyhedral scheme and the pro- posed method. Local errors, represented as colors on the surface, were computed relative to exact polyhedral distances computed at a high-resolution sampled mesh of the contin- uous surface, as described in Section 3.3
Figure 6: Generalization to arbitrary shapes. Top row: Iso-contours shown for our method. Bottom row: errors presented (left to right) for the heat method, fast marching, Lichtenstein et al. and the proposed method. Local errors presented as colors on the surface (brighter color indicates higher error), were computed relative to the polyhedral distances. The evaluation was conducted on TOSCA whereas our solver and the solver proposed by Lichtenstein et al. were trained with only limited number of 2nd order polynomial surfaces (the 3 surfaces presented in Table
4.4 ABLATION STUDY
To amalyze the performance and robustness of our method, we conduct additional tests. These include modifying the local numerical support by which neighborhoods are defined and the precision point representation of the network weights.
8

---

Under review as a conference paper at ICLR 2023
L loss
L loss
10-1
10
10-2
10
10
Accuracy
10-3
0.98
Ring: 2:63
Accuracy
Ring: 3.02
10
Ring 2.97
10-1
flo0854 3.02
0.1
0.1
(a)
(b)
Figure 7: (a) Local neighborhood: Evaluation of the proposed method on spheres with different local neighborhoods support. Ring, corresponds to a neighborhood containing all vertices with at most edges from the evaluated target. (b) Precision floating point representation: Evaluation of our method on spheres with different precision floating point representation of the neural network weights.
Local Neighborhood Support. In the fast-mane fast-narching method, the solver locally estimates solution approximation of the gradient. This approximation
to the cikonal equation using of the gradient is defined by a local stencil. For example, in the case of regularly sampled grids, the one-sided difference formula for a third order approximation requires stencil with three neighbor- analogy to the stencil, our method uses a 3rd ring neighborhood. Our local solver does not explicitly solve eikonal equation nor does it use approximation of the gradient. Yet, the size of the numerical support is the underlying ingredient that allows our neural network to realize high order accuracy. We have empirically validated this, depicted in Figure 7a
ing points (Fornberg. 1988).
Precision Floating Point Representation. The choice of numerical representation is an important decision in the implementation of neural network based solver. It leads trade-off between the accuracy of the solver and its execution time and memory footprint. In all our experiments, our main focus on the accuracy the method. Hence, we used double precision floating point for our neural network implementation. Figure 77b shows a comparison between our implemented network with different precision, showing only a slight degradation when single and half precision floating points are used.
CONCLUSIONS
A fast and accurate method for computing geodesic distances surfaces was presented. Inspired by Lichtenstein et al. (2019) we revisited the ingredients of dynamic programming based distance computation methodologies to designed neural network based local solver. While the local solver proposed by Lichtenstein was limited to second order, we were able to lift this practical barrier by (I) extending the solver numerical support and (2) providing accurate high-order distances to train our solver for general surfaces for which there is no analytic expression for geodesic distances. We trained neural network to locally extrapolate the values of the distance function on sampled surfaces. The result is higher accuracy method compared to state of the art solvers while keeping the low quasi-linear computational complexity. distance function, the proposed solver is trained using an extended local numerical support (more neighboring points). For third order accuracy, the neighborhood consists of all vertices connected to the target point by path with at most three edges. To train our solver using accurate examples, we proposed a novel multi-resolution generation bootstrapping technique that projects distances computed at high resolutions to lower ones. We believe that the proposed bootstrapping idea could be utilized for training other numerical solvers while keeping in mind that the numerical support enables the required accuracy.
achieve more accurate approximation of the

---

Under review as a conference paper at ICLR 2023
REFERENCES
Shahnawaz Ahmed, Stanley Bak, Joyce R. Mclaugg and Daniel Renzi. A third order accurate fast marching method for the eikonal equation in two dimensions. SIAM Journal on Scientific Computing, 33(5):2402-2420, 2011.
Umair bin Waheed, Ehsan Haghighat, Tariq Alkhalifah, Chao Song, and Qi Hao. Pinneik: Eikonal solution using physics-informed neural networks. Computers Geosciences, 155:104833, 2021.
Alexander M. Bronsteen, Michael M. Bronstein, and Ron Kimmel. Numerical geometry of non-rigid shupes. Springer Science & Business Media, 2008.
Keenan Crane, Clarisse Weischedel, and Max Wardetzky. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Transactions on Graphics (TOG), 32(5);1-11, 2013.
Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, (1):269-271, 1959.
Asi Elad and Ron Kimmel. Bending invariant representations for surfaces. In Proceedings of the 2001 IEEE Computer Sociery Conference on Computer Vision and Pattern Recognition. CVPR 2001, volume pp. I-I. IEEF, 2001.
Bengt Fornberg. Generation of finite difference formulas on arbitrarily spaced grids. Mathematics of computation, 51(184):699-706 1988.
Daniel Greenfeld, Meirav Galun, Ron Kimmel, Irad Yavneh, and Ronen Basri. Learning to optimize multigrid pde solvers, In International Conference Machine Learning, pp. 2415-2423, PMLR, 2019.
Jun-Ting Hsich, Shengjia Zhao, Stephan Eismann, Lucia Mirabella, and Stefano Ermon. Learning neural pde solvers with convergence guarantees. arXiv preprint arXiv: 20000000000,,,00 2019.
Shu-Ren Hysing and Stefan Turek. The eikonal equation: numerical efficiency vs. algorithmic complexity quadrilateral grids. In Proceedings of ALGORITMY, volume 22, 2005.
Adrian Ion, Nicole M Artner, Gabriel Peyré, Salvador B López Mármol, Walter G Kropatsch, and
Laurent Cohen. shape matching by geodesic eccentricity. In 2008 IEEE Computer Society Conference Computer Vision and Pattern Recognition Workshops, pp. 1-8. IEEE, 2008
Ron Kimmel and Ron Maurer. Method of computing sub-pixel euclidean distance maps, Septem- ber 26 2006. Application filed Dec. 2000, US Patent 7,113.617.
Ron Kimmel and Guillermo Sapiro. Shortening three-dimensional curves via two-dimensional flows. Computers & Mathematics with Applications, 29(3):49-65 1995.
Ron Kimmel and James A. Sethian. Computing geodesic paths manifolds. Proceedings of the national academy of Sciences, 95(15):8431-8433 1998.
Ron Kimmel and James A. Sethian. Optimal algorithm for shape from shading and path planning. Journal of Mathematical Imaging and Vision, 14(3):237-244 224, 2001.
Ron Kimmel, Nahum Kiryati, and Alfred M. Bruckstein. Multivalued distance maps for motion planning on surfaces with moving obstacles. IEEE Transactions on Robotics and Automation, 14 (3):4774433) 1998.
Fengyan Li, Chi- MaigWang Shu, Yong-Tao Zhang, and Hongkai Zhao. second order discontinuous galerkin fast sweeping method for eikonal equations. Journal of Computational Physics, 227(17): 8191-8208, 2008
Moshe Lichtenstein, Gautam Pai, and Ron Kimmel. Deep eikonal solvers. International Confer- on Scale Space and Variational Methods in Computer Vision, pp. 38-50. Springer, 2019.
Xu Ma. Can Qin, Haoxuan You, Haoxi Ran, and Yun Fu. Rethinking network design and local geometry in point cloud: A simple residual mlp framework. arXiv preprint arXiv:2202.0712. 2022.
10

---

Under review as a conference paper at ICLR 2023
Joseph S.B. Mitchell, David M. Mount, and Christos H. Papadimitriou. The discrete geodesie prob- lem. SIAM Journal on Computing, 16(4):647-66 -68, 1987.
Stanley Osher and James A. Sethian. Fronts propagating with curvature-dependent speed: Algo- rithms based on hamitton-jccoii formulations. Journal of computational physics, 79(1):12-49, 1988.
Daniele Panozzo, Ilya Baran, Olga Diamanti, and Olga Corkine-Hornune Weighted averages on surfaces. ACM Transactions on Graphics (TOG), 32 2013.
Charles R. Qi. Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 652-660, 2017.
Yipeng Qin, Xiaoguang Han, Hongchuan Yu, Yizhou Yu, and Jianjun Zhang. Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation. ACM Transactions on Graphics (TOG), 1513) 2016.
James A. Sethian. A fast marching level set method for monotonically advancing fronts. Proceedings of the National Academy of Sciences, 93(4):1591 199-1195,, 1996.
James A. Sethian. Level set methods and fast marching methods: evolving interfaces in computa- tional geometry, fluid mechanics, computer vision, and materials science, volume 3. Cambridge university press, 1999.
Gil Shamai and Ron Kimmel. Geodesic distance descriptors. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6410-6418. 2017.
Nicholas Sharp and Keenan Crane. You can find geodesic paths triangle meshes by just flipping edges. ACM Transactions Graphics (TOG), 39(6):1-15, 2020.
Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven J. Gortler, and Hugues Hoppe. Fast exact and approximate geodesics on meshes. ACM transactions on graphies (TOG), 24(3):553- 560, 2005.
Philip Trettner, David Bommes. and Leif Kobbelt. Geodesic distance computation via virtual source propagation. In Computer graphics forum, volume 40, pp. 247-260. Wiley Online Library, 2021.
John N. Tsitsiklis. Efficient algorithms for globally optimal trajectories. IEEE Transactions Automatic Control, 40(9):152--1533 1995.
Ofir Weber, Yohai Devir, Alexander M. Bronstein, Michael M. Bronstein, and Ron Kimmel. Par- allel algorithms for approximation of distance maps parametric surfaces. ACM Transactions on Graphics (TOG), 27 2008
Chunxu Xu, Tuanfeng Y Wang, Yong-Jin Liu, Ligang Liu, and Ying He. Fast wavefront propagation (fwp) for computing exact geodesic distances on meshes. IEEE transactions on visualization and computer graphics, 21(7))822 822-834, 2015.
Xiang Ying. Shi-Qing Xin, and Ying He. Parallel chen-han (pch) algorithm for discrete geodesics. ACM Transactions on Graphics (TOG), 33(1);1-11, 2014.
Hongkai Zhao. A fast sweeping method for eikonal equations. Mathematics of computation, 74 (500)6603-677, 2005.
11

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 EXACT DISTANCES ON A POLYHEDRON APPROXIMATING CONTINUOUS SURFACE ARE SECOND ORDER ACCURATE
A.1.1 SECOND ORDER ACCURATE ON CIRCLES
When considering a polyhedral approximation of continuous surface, the exact distances on the polyhedron would be (h²) approximation distances on the continuous surface. Let us start with a toy example. Assume we try to approximate the circumference of circle with radius 1 in the plane using a regular polygon with n vertices. Let A 25. be the angle of the cireular sector defined "
between two successive sample points the circle. The distance between these points is given by = sin (.). The circumference the circle known to be 2x, while the length approximated by the polygon is nh 2n sin(?
H). The truncation error would then be given by 2T nh
2T 2n sin
m
=
2T
2n
5! )
3!
π
π
3n2
60n
O (n" -)
O(h2).
Note, that this analysis also provides a lower bound on the length estimation error of great circles on sphere. order to analyze the behaviour of more general surfaces approximated by triangulated polyhedral surfaces we will resort to the general proof in A.1.2
A.1.2 SECOND ORDER ACCURACY FOR GENERAL SURFACES
S E - R be a Riemannian two dimensional manifold with effective Gaussian curvature a.c. Let C(s) [0, + S be minimal geodesic connecting two surface points C(0) and C(L) with arclength parametrization s, and the length of C.. We prove that the length C' differs by O(h²) from the sum of the lengths of the cords. These line segments, of length h each as measured in TR3, are defined by a sequence of surface points C(ss) and C(8+11). That is, the length of the approximation y defined by its vertices {C(0), C(s2)...., C(sn-1), ((L)) is given by
T(())
Σ [[((++1) C(si)llss nh,
(8)
differs by (h2) from
L(C) = /'' ds.
(9)
Consider the length parameterization along the line segment with end points C(si) and C(si+ i)
be given by / E 1-h/2, h/2], and assume w.l.o.g. the monotone increasing reparametrization s(t) that would allow us to parametrize the surface geodesic segment between C(s.) and C(s+41). As t is the arclength along the cord connecting the two end points of the line segment, by freedom of parametrization, we could choose [C)(
Next, lets compute the length of C(t) in the ith interval.
( ds
Ls(C(s;), ((s+11) =
hh/2
=
|Cr|dt.
(10)
h/2
Lets expand Cel about 0, by which we have
2²
( d2
[C,(1 = |C,(0) +
Cil
(0)
Gel (0) +...
dt
2
dtz
12

---

Under review as a conference paper at ICLR 2023
Ca) Cel
(0) + f² ( (Cr, Cit)
[C((0)+ +t
(0)
+...
(11)
2 dt |Cil
Let us focus on the second term,
(Ce, Cu)
(Cr,Cu)
Cyl2
x|C,1?
(12)
[Cr]
[cr|
where k is the curvature (normal curvature for a geodesic) of C' at that point. The third term is given by
d
k,/Ci1 + 2x( Cu)
dt
kg/C,13 2n. 2 C
(13)
We conclude with
ds
h/2
Ctllt
-N/2
h/2
1
(CI(() + (w|C.)) (0) +
(n, 2x Cx11 (0) + t.... de
JN/2
C,(0)) + 0 (k. 2n C 9)
(0)
h/2
+ O(h²)
h/2
13
C.(0))++ (R.1C,13 2x ( (0)
24 (
(14)
With our specific selection of C.)) 1, we conclude with the overall error given by
n-
Err
L, hl
h23
Σ
(No + 2x²)
+ 0(h3)
24
_x²²) 0(13)
1
+
24
12
o (())
(15)
where k and are evaluated f for each segment. Note, that and geometric quantities and thus could be regarded as effective bounded constants. Then, by the assumption h O(n -1) proved the convergence rate to be O(h²).
A.2 NEURAL ARCHITECTURE ENGINEERING CONSIDERATIONS
In this research we aim to develop high order accurate methods for computing geodesic distances on surfaces. To overcome the 2nd order restriction of the polyhedral approximation, start with the method presented in Lichtenstein et al. (2019). This method uses a neural network based lo- cal solver that circumvents the polyhedral representation of the surface and operates directly on the neighboring points. In the fast-marching method, the local solver estimates solution to the eikonal equation using a finiteddifference approximation of the gradient. The stencil size in the finite dif- ference method determines the accuracy of the operator (Fornberg 1988). Our hypotheses is that extending the numerical support of the local solver would improve the overall order of accuracy.
In our first attempt examine the neural network presented by Lichtenstein et al. (2019) while extending the local support to 3rd ring neighborhood. Such a direct extension did not improve the accuracy of the method, can be seen in Figure 8 Next, we studied the trained model latent vector obtained after the max max-poolll pooling operation. Out of the 1024 entries of this vector, only 96 were different than zero
13

---

Under review as a conference paper at ICLR 2023
Based this observation experimented with architectural modifications by extending the number of hidden layers, changing the activation functions, and reducing the size of the latent space. These modifications
presented in Table Z where Model is proposed neural architecture presented in F and all other models have a similar architecture up to the changes defined in the table. As be in Figure [ the various architectural changes have large impact on the performance of the solver.
Table 2: Neural Architectures: Various architectural modifications to our presented neural network The residual connections and the different activation functions defined only for the shared weight MLP, while the fully connected network applied after the pooling operation has LeakyRelu activations with negative slope of 0.001 in all variants of neural network.
2]
Neural architecture
Residual connections
Activation Function
negative slope
Pooling operation
Model
LeakyReLu
0.2
max
Model
LeakyReLu
0.2 (.001(default)
avg
Model 3
LeakyReLu
max
Model 4
ReLu
X
max
Model
X
ReLu
x
Lichtenstein et al.
ReLu
X
max
L1 loss
10-1
10-2
Error
Accuracy
10-3
Model 1 3.02
Model 2.59
Model 3 2.73
Model 4 2.38
Model 5 2.22
10-4
Lichtenstein et al. 1.91
0.1
Figure 8: Neural architectures: Evaluation the effects of different modifications to our neural network, presented in [ All different models the local neighborhood support, which includes vertices with at most three edges from the evaluated target.
A.3 ROBUSTNESS TO TRIANGULATION
The proposed local solver applied directly to the mesh points, and does not use the underlying triangulation. However, the numerical support of the solver and the distance updating scheme do depend on the triangulation. Therefore, is important to investigate the robustness our method to various triangulation methods. Ones that was not part of the training of the proposed solver.
14

---

Under review as a conference paper at ICLR 2023
Table 3: Generalization arbitrary shapes: Quantitative evaluation tested on TOSCA. The enrors are relative to the polyhedral scheme. Our solver and the solver proposed by Lichtenstein et al. were trained using our bootstrapping method 3.3 with very limited number of 2nd order polynomial surfaces (the 3 surfaces presented in Table
Shape
L.0
Heat
FMM
Lichtensiein
Heal
FMM
Lichtenstein
Dog
0.0728
0.0110
0.0123
0.0037
0.8688
0.1514
0.1318
0.0465
Cat
0.1596
0.0136
0.0386
0.0053
0.6541
0,0631
0.3450
0.0384
Wolf
0.0440
0.0162
0.0169
0.0072
0.2244
0.1009
0.1343
0.0422
Horse
0.1084
0.0136
0.0199
0.0068
0,8239
0.2273
0.1616
0.0896
Michael
0.1185
0.0109
0.1073
0.0054
0.5906
0,1602
0.4873
0.0881
Victoria
0.1211
0.0076
0.0479
0.0027
0.4538
0.1075
0.2289
0.0414
Centaur
0.0672
0.0188
0.1088
0.0062
4.9437
0.1985
0.7348
0.1417
Heat
FMM
Lichtenstein et al.
Ours
Exact
Figure 9: Generalization to arbitrary shapes: Iso-contours shown for (left to right) the heat method, fast marching. Lichtenstein et al., our method and the exact polyhedral scehme, calculated by the MMP algorithm. The evaluation was conducted the solver proposed by Lichtenstein et al. were trained with only limited number of 2nd order polynomial surfaces (the 3 surfaces presented in Table
shapes from TOSCA whereas solver and
In a new experiment we train our neural network on regularly sampled spheres and evaluate the resulting solver arbitrarily triangulated spheres that includes ill-posed triangles. We show the numerical and qualitative evaluation in Table g and Figure I0 can be seen that the proposed method is robust to different triangulations and produces lower emrrr compared to the heat method,
15

---

Under review as a conference paper at ICLR 2023
the classical fast marching, the exact geodesic method, and the deep learning method of Lichtenstein et al.
Table Robustness to triangulation: Quantitative evaluation of the ability of the proposed method to handle triangulations other than those for which it was trained for. The evaluation was conducted on randomly uniformly non-regularly sampled spheres whereas our solver and the solver proposed
by Lichtenstein et al. were trained only on regularly sampled spheres.
Error
FMM
Heat method
Lichtenstein et al.
MMP
Ours
L1
0.01804
0.01964
0.00510 10
0.00128
0.00099
L2
0.01865
0.02048
0,00672
0.00142
0.00127
Loo
0.0270
0.0361
0.02278
0.0027
0.0041
Ours
MMP
0.00
0.00104
0,00208
0,00312
0.00417
Figure 10: Robustness to Triangulation: Errors presented for the "exact" MMP scheme and proposed method. Local errors, represented as colors on the surface, were computed relative to the analytical geodesic distances. The proposed method was trained on regularly sampled spheres as can be seen in Figure 12
A.4 THE UPDATE STEP COMPLEXITY
Theoretically, our method has the same quasi-linear computational complexity as the fast marching method and the method presented by Lichtenstein al. (2019). all of which relies on the distance updating scheme presented in Algorithm I The different local solvers, while having O(1) compu- tation complexity, involve different constants.
A single update step of the proposed method requires 1537us, single update step in Lichtenstein al. (2019) requires 788μs, while an update the fast marching method requires only 6.3ps Hence, the fast marching is approximately 250 times faster when applied to the same grid resolution. And yet, the high order accuracy allows us to sub-sample our triangulated surfaces and save on overall complexity achieving the same goals.
16

---

Under review as a conference paper at ICLR 2023
Lg loss
Li loss
10-
10
Ero
Apcuracy
Accurady
1.74
MVP
10
0.1
0.2
0.5
0.5
(a)
(b)
Figure 11: Order of accuracy on parametric surfaces: Plots showing the effect of the edge size on the errors. The accuracy of each scheme associated with its corresponding slope. Ground truth distances were evaluated using our bootstrapping method 3.3 (a) Evaluation on hyperbolic
paraboloid z" y². (b) Evaluation on regular paraboloid x² +
0.0.
6.7
13.4
20N1
26.8
Figure 12: Attention map showing the importance of each neighboring point in the network approx- imation. The source point colored pink, the point whose distance currently evaluated is colored red, and all other plotted points form the current local neighborhood. The Visited neighboring points that fed into the neural network are colored according to the percentage of the corresponding features in the latent vector obtained from the max-pooling operation.
17


Reviews:
[{"review_id": "iGM1iwSydOB", "reviewer": "Reviewer_58bg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a learning-based method for computing geodesics on a triangulated mesh. The algorithm is similar to fast marching cubes with O(NlogN) complexity, except the distance updating step which is the one of the two main contributions of the paper.\nThe proposed distance update step encodes the 3-ring neighbors along with distances from the source (normalised such that norm of distances is 1) using Pointnet (existing method for encoding 3d data) to get a representation of each neighborhood. Then the method tries to train this encoder on ground truth data in a supervised fashion.\nThe second main contribution is that, since the method is computing local geodesics, it is trained on spherical surfaces (simple analytical surfaces)  where an exact computation of geodesics is possible. The training is completely supervised. It is very easy to see that once trained on this data, the method can be easily extended to any complex shape.\nThe experiments demonstrate superior geodesic computation wrt main sota methods.", "summary_of_the_review": "I think that the technical novelty is limited and the lack of experimental evaluation does not allow me to overlook that part. Had it been a (learning-based) method X times faster and X times more accurate (accuracy has been demonstrated partially on polynomial surfaces) on real data (TOSCA, but some other datasets. should have been used as well), my opinion could have been different as it could have been a method with limited novelty but significantly improved performance.", "strength_and_weaknesses": "Strengths:\n1. The method is simple. Can generalise to complex shapes easily.\n2. The paper is well-written. The proposed concepts are well-explained. There are enough details in the paper to reproduce the method.\n3. The results show a huge improvement over sota.\n\nWeakness:\n1. The technical novelty is limited to using pointnet features to learn geodesic distances. \n2. My main concern is the experiment section. The complexity of the method is mentioned but the concrete timing performance of the method is never talked about. I understand that the distance update steps is going to expensive but it is important to see the difference.\n3. The quantitative evaluation is missing on TOSCA dataset. The authors should have reported the geodesic computation accuracy on this dataset and should have compared with other methods such as FMM, MMP and Lichtenstein et al. Perhaps, MMP can be used as baseline.\n4. Since the method is trained on spheres of arbitrary radii (assuming that they vary between extremely small and large), it would have been nice to see the localised performance comparison on the sharp regions such as cat ears, dog-tails etc.\n5. FMM is missing from table 1.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "h1iDQkF38W", "reviewer": "Reviewer_ssEx", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper formulates a third-order accurate fast-marching style algorithm for finding geodesic distances on surfaces embedded in 3D. The local solver is a trained neural network which operates on the 3-ring of the point in question. The algorithm has quasilinear complexity ultimately. For training, a multi-resolution approach is used, resulting in a method that can find distances on coarse meshes that are more accurate than would be possible with exact methods.\n\nThe method is compared to an exact solver, MMP, and a related work Liechtenstein et al. which looks at the 2-ring and forms a second-order accurate scheme. The comparisons are favorable. Ablation studies show that increasing the neighborhood support further does not improve the accuracy of the method.", "summary_of_the_review": "The strengths and weaknesses above summarize my main thoughts on the work. I feel that the work is well-written and investigated, with clear motivation and rationale behind the method. Moreover, it improves upon existing methods, so I am for acceptance.", "strength_and_weaknesses": "Strengths:\n- Well-written and clear\n- The approach clearly improves upon existing methods, including one with a related approach (Liechtenstein et al.).\n- A simple and sensible neural network architecture is used.\n\nWeaknesses:\n- As Liechtenstein et al. considered a very similar idea already, it could be argued that the method does not have sufficient novelty.\n- The work does not explore the use of other neural network architectures for the local solver, or at least does not comment on it.\n- It is unclear if the experiments show robustness to the quality of the triangulations for the underlying meshes. Certainly, it seems that the training set triangulations are well-conditioned, so it'd be curious to see its behavior on poorly conditioned meshes. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5oq2CukoZIC", "reviewer": "Reviewer_UqX8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper extends the Deep Eikonal Solver of Liechtenstein et al. It achieves higher empirical accuracy by allowing the local solver to see a 3-ring rather than 2-ring neighborhood, and by training against ground truth distances computed on a finer mesh. The results display generalization from polynomial surfaces to surfaces from the TOSCA dataset.", "summary_of_the_review": "The paper shows some very accurate results in limited evaluations, building on the work of Liechtenstein et al. However, it makes some very strong and unsubstantiated claims that would require more extensive empirical evaluation of generalization performance to justify.", "strength_and_weaknesses": "## Strengths\n- The method is presented fairly clearly.\n- The few results that are presented look good—namely Figure 4 showing empirical distance accuracy of order $h^3$ on meshes of a sphere, and Figure 6 showing better accuracy than competing methods on a dog mesh.\n## Weaknesses\n- The method is claimed to be 3rd-order accurate, i.e., $\\mathcal{O}(h^2)$ throughout the paper. However, this appears to be only an empirical statement based on evaluation on spheres. If you want to claim this accuracy, more evaluation is necessary, especially on real data surfaces from TOSCA. The evaluation of generalization from polynomial surfaces to TOSCA surfaces is very quick and only visual. A more careful and comprehensive numerical evaluation of generalization to the TOSCA dataset is necessary to make a convincing case that this method is highly accurate.\n- The paper claims that \"exact geodesic distances computed on a polygonal mesh approximating a continuous surface would be at most a second order approximation,\" and Appendix A provides an argument to that effect. However, the argument is restricted to a very special case (polygonal approximation of circles in the plane), and it is not a proof. Moreover, no proof is cited. To make a strong claim like this, proof or citation should be given.\n- Section 3.3 (bottom of page 6) claims that the bootstrapping approach can achieve arbitrary accuracy. This seems like it would only be true if the generalization error of your learned local solver is zero. Please provide further justification or else remove these claims.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject