# A comparison of three optimal algorithms for the canonization of circular strings

Iliopoulos, C.S. and Smyth, W.F.
(1989)
*A comparison of three optimal algorithms for the canonization of circular strings.*
Journal of Combinatorics, Information & System Sciences, 14
(2/3).
pp. 59-72.

## Abstract

Every position i in a given circular string A of length n gives rise to a linear string A[i],...,A[n],A[1],···,A[i-1]. It is required to determine every position in A which begins a linear string that is lexicographically least over all linear strings of A. There are three quite different sequential algorithms, due to K. S. Booth [Inf. Process. Lett. 10, 240-242 (1980; Zbl 0444.68064)], Y. Shiloach [J. Algorithms 2, 107-121 (1981; Zbl 0459.68035)], and the authors [A new sequential algorithm for canonization of circular strings, submitted for publication], which solve this problem in O(n) time, and which are therefore asymptotically optimal. We provide overviews of these algorithms, together with an analysis of their performance in important cases; we also report on comparisons among them, based on two measures of complexity: number of “tests” and run time. The algorithms have application to computational geometry; in particular, to the determination of whether or not two given n-gons are similar.

Item Type: | Journal Article |
---|---|

Publisher: | MDPPL |

Publishers Website: | http://www.mdppl.in/ |

URI: | http://researchrepository.murdoch.edu.au/id/eprint/27405 |

Item Control Page |