Finding the shortest path or distance between two points on a surface S in three-dimensional space is an important problem in both differential geometry and computational geometry. When referring to S, the shortest path is known as a geodesic path, while the shortest distance is known as a geodesic distance. The computation of geodesic paths and distances on polyhedral surfaces finds applications across various domains such as robotics, geographic information systems (GIS), circuit design, mesh manipulation, medical treatments like radiation therapy, dental procedures, and computer graphics. For instance, geodesic path calculations can be utilized to determine the most efficient route for a robotic arm to traverse without encountering obstacles, analyze water flow, manage traffic, handle texture mapping and deformation, as well as facilitate facial recognition.
In this project, we will focus on scenarios where a discrete representation of surface S is provided, specifically as a polyhedron P in three-dimensional space. Due to the non-differentiability of discrete surfaces, traditional methods from differential geometry for computing geodesic paths and distances are not directly applicable. Nevertheless, techniques from this field can be adapted and extended to the discrete setting. Additionally, viewing the discrete surface as a graph in three-dimensional space enables the utilization of methods from graph theory and computational geometry to find geodesic paths and distances on polyhedral surfaces. We will adopt the following criteria for evaluation:
- Accuracy of the computed geodesic path;
- The cost metric employed in computing the geodesic path;
- The space complexity of the proposed algorithm;
- The time complexity of the proposed algorithm;
- Applicability of the algorithm through implementation and testing in real-world scenarios.
Requirements
Students are required to have a solid background in algorithms and excellent programming skills in C/C++/Java. ANU students are expected to have finished COMP3600 or have an equivalent experience.
References
- A survey of geodesic paths on 3D surfaces, P Bose, A Maheshwari, C Shu, S Wuhrer - Computational Geometry, 2011
- Algorithms for approximate shortest path queries on weighted polyhedral surfaces, L Aleksandrov, HN Djidjev, H Guo, A Maheshwari, D Nussbaum, JR Sack, Discrete & Computational Geometry 44 (4), 762-801, 2010