GeodesicEmbedding (GE): A High-Dimensional Embedding Approach for Fast Geodesic Distance Queries.

Area of Science:

• Computer Graphics
• Computational Geometry
• Differential Geometry

Background:

• Geodesic distance computation is crucial in various fields.
• Existing methods for geodesic distance queries can be computationally expensive.
• High-dimensional embedding offers a potential avenue for efficient distance calculations.

Purpose of the Study:

• To develop a novel and efficient method for fast geodesic distance queries on manifold surfaces.
• To address the computational challenges of high-dimensional embedding for geodesic distance approximation.
• To improve the speed and accuracy of geodesic distance calculations in computer graphics and related fields.

Main Methods:

• Embedding mesh surfaces into a high-dimensional space where Euclidean distance approximates geodesic distance.
• Reducing problem complexity by embedding only saddle vertices and locally embedding non-saddle vertices.
• Employing a cascaded optimization approach with non-Euclidean functions to minimize approximation errors.

Main Results:

• The proposed method significantly reduces the complexity of high-dimensional embedding for geodesic distance queries.
• A cascaded optimization strategy effectively minimizes approximation errors, enhancing accuracy.
• The developed approach enables near-constant time geodesic distance queries after precomputation.

Conclusions:

• The novel method provides a highly efficient solution for geodesic distance queries.
• This technique offers a significant improvement over previous geodesic distance query methods.
• The approach demonstrates the feasibility of using optimized high-dimensional embeddings for geometric computations.