Parallel circle-cover algorithms (Q1108792)

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^ 2 n)\) 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+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.