Shortest circular paths on planar graphs

D.S. Farin, P.H.N. With, de

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)

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 languageEnglish
Title of host publicationProc. of 27th Symposium on Information Theory in the Benelux, June 8-9, 2006, Noordwijk, The Netherlands
EditorsR.L. Lagendijk, Jos H. Weber, A.F.M. Berg, van den
Place of PublicationEefde
PublisherWerkgemeenschap voor Informatie- en Communicatietheorie (WIC)
Pages117-124
ISBN (Print)90-71048-22-5
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'Shortest circular paths on planar graphs'. Together they form a unique fingerprint.

Cite this