Home
Scholarly Works
PRAM algorithms for identifying polygon similarity
Journal article

PRAM algorithms for identifying polygon similarity

Abstract

The computation of the least lexicographic rotation of a string leads to the identification of polygon similarity. An O(logn) time CRCW PRAM algorithm for computing the least lexicographic rotation of a circular string (of length n) over a fixed alphabet is presented here. The logarithmic running time is achieved by using O(n/logn) processors and its space complexity is linear. A second algorithm for unbounded alphabets requires O(lognloglogn) units of time, uses O(n/logn) processors.

Authors

Iliopoulos CS; Smyth WF

Journal

Lecture Notes in Computer Science, Vol. 401, , pp. 25–32

Publisher

Springer Nature

Publication Date

January 1, 1989

DOI

10.1007/3-540-51859-2_4

ISSN

0302-9743
View published work (Non-McMaster Users)

Contact the Experts team