Shortest circular paths on planar graphs
D. Farin · 2006
The shortest circular-path problem is similar to the ordinary shortest path problem, but instead of specifying a distinguished starting and end node, the path has to form a closed loop. This problem has several applications in optimization problems as they occur in image segmentation or shape matching. We propose a new algorithm to compute shortest circular paths on planar graphs that has a typical computation time of O(lVllog IVI) and a worst case complexity of (lVllog2 1V1). The fastest previously known algorithm for this problem has an average computation time of O(lVllog2 IVI) and a worst case performance of O(1V1210g IVI)·