Conflict-free colorings of shallow discs

Noga Alon, Shakhar Smorodinsky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations

Abstract

We prove that any collection of n discs in which each one intersects at most k others, can be colored with at most O(log3 k) colors so that for each point p in the union of all discs there is at least one disc in the collection containing p whose color differs from that of all other members of the collection that contain p. This is motivated by a problem on frequency assignments in cellular networks, and improves the best previously known upper bound of O(log n) when k is much smaller than n.

Original languageEnglish (US)
Title of host publicationProceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
PublisherAssociation for Computing Machinery (ACM)
Pages41-43
Number of pages3
ISBN (Print)1595933409, 9781595933409
DOIs
StatePublished - Jan 1 2006
Externally publishedYes
Event22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States
Duration: Jun 5 2006Jun 7 2006

Publication series

NameProceedings of the Annual Symposium on Computational Geometry
Volume2006

Other

Other22nd Annual Symposium on Computational Geometry 2006, SCG'06
CountryUnited States
CitySedona, AZ
Period6/5/066/7/06

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Keywords

  • Conflict-free coloring
  • Frequency-assignment
  • Wireless

Fingerprint Dive into the research topics of 'Conflict-free colorings of shallow discs'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., & Smorodinsky, S. (2006). Conflict-free colorings of shallow discs. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06 (pp. 41-43). (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006). Association for Computing Machinery (ACM). https://doi.org/10.1145/1137856.1137864