Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
PRAM algorithms for identifying polygon similarity
| Book Series | Lecture Notes in Computer Science |
| Publisher | Springer Berlin / Heidelberg |
| ISSN | 0302-9743 (Print) 1611-3349 (Online) |
| Volume | Volume 401/1989 |
| Book | Optimal Algorithms |
| DOI | 10.1007/3-540-51859-2 |
| Copyright | 1989 |
| ISBN | 978-3-540-51859-4 |
| DOI | 10.1007/3-540-51859-2_4 |
| Pages | 25-32 |
| Subject Collection | Computer Science |
| SpringerLink Date | Saturday, January 21, 2006 |
| |
|
PRAM algorithms for identifying polygon similarity Costas S. Iliopoulos1 and W. F. Smyth2
| (1) |
Department of Computer Science, Royal Holloway College, University of London, TW20 0EX Egham, England |
| (2) |
Department of Computer Science and Systems, McMaster University, L8S 4K1 Hamilton, Ontario, Canada |
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.
This work of both authors was partially supported by the GR/E 75752 grant of the Science and Engineering Reserch Council of the UK. The first author was supported in part by the UK SERC GR/F 00898 grant and a Royal Society grant. The work of the second author was partially supported by grant No A8180 of the Natural Sciences and Engineering Council of Canada
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|