Conflict-Free Coloring for Rectangle Ranges Using O(n .382) Colors

Files in This Item:
File Description SizeFormat 
ajwani_dcg12.pdf142.67 kBAdobe PDFDownload
Title: Conflict-Free Coloring for Rectangle Ranges Using O(n .382) Colors
Authors: Ajwani, DeepakElbassioni, KhaledGovindarajan, SathishRay, Saurabh
Permanent link:
Date: 28-Apr-2012
Online since: 2019-04-10T11:57:36Z
Abstract: Given a set of points P ⊆ ℝ 2, a conflict-free coloring of P w. r. t. rectangle ranges is an assignment of colors to points of P, such that each nonempty 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 base stations (points) such that within any range (for instance, rectangle), there is no interference. We show that any set of n points in ℝ 2 can be conflict-free colored with O(n β*+o(1)) colors in expected polynomial time, where β∗=3−5√2<0.382.
Type of material: Journal Article
Publisher: Springer
Journal: Discrete and Computational Geometry
Volume: 48
Issue: 1
Start page: 39
End page: 52
Copyright (published version): 2012 Springer
Keywords: Frequency assignment in wireless networksConflict-free coloringAxis-parallel rectanglesBoundary setsMonotone sequences
DOI: 10.1007/s00454-012-9425-5
Language: en
Status of Item: Peer reviewed
Appears in Collections:Computer Science Research Collection

Show full item record

Citations 20

Last Week
Last month
checked on Oct 12, 2019

Google ScholarTM



This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.