Coloring geometric range spaces Academic Article uri icon


  • Abstract We study several coloring problems for geometric range-spaces. In addition to their theoretical interest, some of these problems arise in sensor networks. Given a set of points in ℝ 2 or ℝ 3, we want to color them so that every region of a certain family (eg, every disk containing at least a certain number of points) contains points of many (say, k) different colors. In this paper, we think of the number of colors and the number of points as functions of k. Obviously, for a fixed k using k colors, it is not always possible to ensure that every region containing k points has all colors present. Thus, we introduce two types of relaxations: either we allow the number of colors used to increase to c (k), or we require that the number of points in each region increases to p (k). Symmetrically, given a finite set of regions in ℝ 2 or ℝ 3, we want to color them so that every point covered by a sufficiently …

publication date

  • January 1, 2009