Parallelization of the funnel tree algorithm for finding shortest paths on polyhedral surfaces

Abstract

This paper presents an enhanced approach to computing shortest paths on triangulated polyhedral surfaces by parallelizing the Funnel Tree Algorithm (introduced by An et al. in The funnel tree algorithm for finding shortest paths on polyhedral surfaces, Optimization (2023)) and incorporating the Method of Orienting Curves. In particularly, we use the Method of Orienting Curves for finding the shortest path from the cusp of a funnel to its direct destination. As a result, the children of the funnel are also determined simultaneously. This combined approach leverages modern multi-core processors to achieve significant performance improvements. Experimental results demonstrate the effectiveness of this method on various polyhedral surfaces. The resulting implementation achieves significantly better speedups over corresponding sequential code given by An et al. when compared to their previous work.