On conflict-free coloring of points and simple regions in the plane

Sariel Har-Peled, Shakhar Smorodinsky

Research output: Contribution to conferencePaper

Abstract

In this paper, we study coloring problems related to frequency assignment problems in cellular networks. In abstract setting, the problems are of the following two types: CF-coloring of regions: Given a finite family S of n regions of some fixed type (such as discs, pseudo-discs, axis-parallel rectangles, etc.), what is the minimum integer k, such that one can assign a color to each region of S, using a total of at most k colors, such that the resulting coloring has the following property: For each point p ∈ ∪b∈Sb there is at least one region b ∈ S that contains p in its interior, whose color is unique among all regions in S that contain p in their interior (in this case we say that p is being 'served' by that color). We refer to such a coloring as a conflict-free coloring of S (CF-coloring in short). CF-coloring of a range space: Given a set P of n points in ℝd and a set R of ranges (for example, the set of all discs in the plane), what is the minimum integer k, such that one can color the points of P by k colors, so that for any r ∈ R, with P ∩ r ≠ θ, there is at least one point q ∈ P ∩ r that is assigned a unique color among all colors assigned to points of P ∩ r (in this case we say that r is 'served' by that color). We refer to such a coloring as a conflict-free coloring of (P, R) (CF-coloring in short).

Original languageEnglish (US)
Pages114-123
Number of pages10
StatePublished - Jul 28 2003
EventNineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States
Duration: Jun 8 2003Jun 10 2003

Other

OtherNineteenth Annual Symposium on Computational Geometry
CountryUnited States
Citysan Diego, CA
Period6/8/036/10/03

    Fingerprint

Keywords

  • Cellular Network
  • Coloring
  • Frequency Assignment

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Cite this

Har-Peled, S., & Smorodinsky, S. (2003). On conflict-free coloring of points and simple regions in the plane. 114-123. Paper presented at Nineteenth Annual Symposium on Computational Geometry, san Diego, CA, United States.