Title :
Optimal overlap representations
Author_Institution :
FRL, Los Angeles, CA, USA
Abstract :
In this paper, we investigate the problem of computing minimal interval and circular arc overlap representations, and give several optimal algorithms. We show that, among other things, given an s×t interval or circular arc overlap representation matrix: a minimal interval overlap representation can be obtained with O(log(st)) time with O(st/log(st)) EREW PRAM processors, or in O(log t/log log t) time with O(st log log t/log t) common CRCW PRAM processors, or in O(1) time with O(st) BSR processors; a minimal circular arc overlap representation can be obtained in O(st) time
Keywords :
computational complexity; computational geometry; parallel algorithms; BSR processors; EREW PRAM processors; circular arc overlap representations; common CRCW PRAM; minimal interval; minimal interval overlap representation; optimal algorithms; optimal overlap representations; Clocks; Parallel algorithms; Phase change random access memory;
Conference_Titel :
Parallel Architectures, Algorithms, and Networks, 1996. Proceedings., Second International Symposium on
Conference_Location :
Beijing
Print_ISBN :
0-8186-7460-1
DOI :
10.1109/ISPAN.1996.508954
