Abstract
Given a set of
n circular arcs, we provide an optimal parallel algorithm (on the CREW PRAM model of computation) for finding a minimum number of circular arcs whose union covers the circle. The algorithm runs in O(log
n) time with O(
n) processors and uses O(
n) space. This is a significant improvement over the recent algorithm by Bertossi that runs in O(log
n) time with O(
n
2) processors and uses O(
n
2) space.
