PARALLEL CIRCLE-COVER ALGORITHMS

Given a set of n circular-arcs, each possibly having a real weight, we consider the problem of finding a subset of the arcs whose union covers the whole circle. We provide parallel algorithms running in O(log n) and O(log **2n) time, respectively, for finding a circle-cover with the smallest number of arcs and with the smallest overall weight. The algorithms require, respectively, O(n**2/log n plus qn) and O(n**3/log n) processors on a shared memory model (SMM) of parallel computers, where q-1 is the minimum number of arcs crossing any point of the circle.