Optimal Circular Arc Representations: Properties, Recognition, and Construction

摘要

We investigate some properties of minimal interval and circular arc representations and give several optimal sequential and parallel recognition and construction algorithms. We show that, among other things, given ans×tinterval or circular arc representation matrix,  • deciding if the representation is minimal can be done inO(log s) time withO(st/log s) EREW PRAM processors, or inO(1) time withO(st) common CRCW PRAM processors;  • constructing an equivalent minimum interval representation can be done inO(log(st)) time withO(st/log(st)) EREW PRAM processors, or inO(log t/log log t) time withO(st log log t/log t) common CRCW PRAM processors, or inO(1) time withO(st) BSR processors;  • constructing an equivalent minimal circular arc representation can be done inO(st) time.