Applying the improved Chen and Hans algorithm to different versions of shortest path problems on a polyhedral surface
The computation of shortest paths on a polyhedral surface is a common operation in many computer graphics applications. There are two best known exact algorithms for the single source, any destination shortest path problem. One is proposed by Mitchell etal. (1987) [1]. The other is by Chen and Han (1990) [11]. Recently, Xin and Wang (2009) [9] improved the CH algorithm by exploiting a filtering theorem and achieved a practical method that outperforms both the CH algorithm and the MMP algorithm whether in time or in space. In this paper, we apply the improved CH algorithm to different versions of shortest path problems. The contributions of this paper include: (1) For a surface point p??v1v2v3 p ? ? v 1 v 2 v 3 , we present an unfolding technique for estimating the distance value at p using the distances at v1,v2 v 1 , v 2 and v3 v 3 . (2) We show that the improved CH algorithm can be naturally extended to the multiple sources, any destination version. Also, introducing a well-chosen heuristic factor into the improved CH algorithm will induce an exact solution to the single source, single destination version. (3) At the conclusion of multi-source shortest path algorithms, we can use the distance values at vertices to approximately compute the geodesic-distance-based offsets, the Voronoi diagram and the Delaunay triangulation in O(n) O ( n ) time. (4) By importing a precision parameter ? ? , we obtain a precision controlled approximant which varies from the improved CH algorithm to Dijkstras algorithm as ? ? increases from 0 0 to 1 1 . Thus, an interesting relationship between them can be naturally established.
voronoi diagram computational geometry discrete geodesic problem