Abstract
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)·
| Original language | English |
|---|---|
| Title of host publication | Proc. of 27th Symposium on Information Theory in the Benelux, June 8-9, 2006, Noordwijk, The Netherlands |
| Editors | R.L. Lagendijk, Jos H. Weber, A.F.M. Berg, van den |
| Place of Publication | Eefde |
| Publisher | Werkgemeenschap voor Informatie- en Communicatietheorie (WIC) |
| Pages | 117-124 |
| ISBN (Print) | 90-71048-22-5 |
| Publication status | Published - 2006 |