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

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