## Abstract

Given a set of points P R^{2}, a conflict-free coloring of P w.r.t. rectangle ranges is an assignment of colors to points of P, such that each non-empty axis-parallel rectangle T in the plane contains a point whose color is distinct from all other points in P T. This notion has been the subject of recent interest, and is motivated by frequency assignment in wireless cellular networks: one naturally would like to minimize the number of frequencies (colors) assigned to bases stations (points), such that within any range (for instance, rectangle), there is no interference. We show that any set of n points in R^{2} can be conflict-free colored with (n^{Β+}) colors in expected polynomial time, for any arbitrarily small > 0 and Β = 3?5<over>2 < 0.382. This improves upon the previously known bound of O(nlog log n/ log n).

Original language | British English |
---|---|

Title of host publication | SPAA'07 |

Subtitle of host publication | Proceedings of the Nineteenth Annual Symposium on Parallelism in Algorithms and Architectures |

Pages | 181-187 |

Number of pages | 7 |

DOIs | |

State | Published - 2007 |

Event | SPAA'07: 19th Annual Symposium on Parallelism in Algorithms and Architectures - San Diego, CA, United States Duration: 9 Jun 2007 → 11 Jun 2007 |

### Publication series

Name | Annual ACM Symposium on Parallelism in Algorithms and Architectures |
---|

### Conference

Conference | SPAA'07: 19th Annual Symposium on Parallelism in Algorithms and Architectures |
---|---|

Country/Territory | United States |

City | San Diego, CA |

Period | 9/06/07 → 11/06/07 |

## Keywords

- Axis-parallel rectangles
- Conflict-free coloring
- Dominating sets
- Frequency assignment in wireless networks
- Monotone sequences

## Fingerprint

Dive into the research topics of 'Conflict-free coloring for rectangle ranges using O(n^{.382}) colors'. Together they form a unique fingerprint.