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, Deepak
Elbassioni, Khaled
Govindarajan, Sathish
Ray, Saurabh
Permanent link: http://hdl.handle.net/10197/9896
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

SCOPUSTM   
Citations 20

10
Last Week
0
Last month
checked on May 17, 2019

Google ScholarTM

Check

Altmetric


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.