  In this paper, we develop a novel method for fast geodesic distance queries.
The key idea is to embed the mesh into a high-dimensional space, such that the
Euclidean distance in the high-dimensional space can induce the geodesic
distance in the original manifold surface. However, directly solving the
high-dimensional embedding problem is not feasible due to the large number of
variables and the fact that the embedding problem is highly nonlinear. We
overcome the challenges with two novel ideas. First, instead of taking all
vertices as variables, we embed only the saddle vertices, which greatly reduces
the problem complexity. We then compute a local embedding for each non-saddle
vertex. Second, to reduce the large approximation error resulting from the
purely Euclidean embedding, we propose a cascaded optimization approach that
repeatedly introduces additional embedding coordinates with a non-Euclidean
function to reduce the approximation residual. Using the precomputation data,
our approach can determine the geodesic distance between any two vertices in
near-constant time. Computational testing results show that our method is more
desirable than previous geodesic distance queries methods.
