Dynamic offline conflict-free coloring for unit disks

Abstract

A conflict-free coloring for a given set of disks is a coloring of the disks such that for any point p on the plane there is a disk among the disks covering p having a color different from that of the rest of the disks that covers p. In the dynamic offline setting, a sequence of disks is given, we have to color the disks one-by-one according to the order of the sequence and maintain the conflict-free property at any time for the disks that are colored. This paper focuses on unit disks, i.e., disks with radius one. We give an algorithm that colors a sequence of n unit disks in the dynamic offline setting using O(logn) colors. The algorithm is asymptotically optimal because Ω(logn) colors is necessary to color some set of n unit disks for any value of n [9]. © 2009 Springer Berlin Heidelberg.