Conflict-Free Coloring for Rectangle Ranges Using O(n .382) Colors
|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 networks; Conflict-free coloring; Axis-parallel rectangles; Boundary sets; Monotone 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
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.