### 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∈S}b 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 language | English (US) |
---|---|

Pages | 114-123 |

Number of pages | 10 |

State | Published - Jul 28 2003 |

Event | Nineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States Duration: Jun 8 2003 → Jun 10 2003 |

### Other

Other | Nineteenth Annual Symposium on Computational Geometry |
---|---|

Country | United States |

City | san Diego, CA |

Period | 6/8/03 → 6/10/03 |

### Fingerprint

### Keywords

- Cellular Network
- Coloring
- Frequency Assignment

### ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

### Cite this

*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.