{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T07:11:03Z","timestamp":1791011463550,"version":"4.1.0"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2003,1]]},"abstract":"<jats:p>Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem that we call minimum conflict-free coloring (min-CF-coloring). In its general form, the input of the min-CF-coloring problem is a set system $(X,{\\cal S})$, where each $S \\in {\\cal S}$ is a subset of X. The output is a coloring $\\chi$ of the sets in ${\\cal S}$ that satisfies the following constraint: for every $x \\in X$ there exists a color i and a unique set $S \\in {\\cal S}$ such that $x \\in S$ and $\\chi(S) = i$. The goal is to minimize the number of colors used by the coloring $\\chi$. Min-CF-coloring of general set systems is not easier than the classic graph coloring problem. However, in view of our motivation, we consider set systems induced by simple geometric regions in the plane. In particular, we study disks (both congruent and noncongruent), axis-parallel rectangles (with a constant ratio between the smallest and largest rectangle), regular hexagons (with a constant ratio between the smallest and largest hexagon), and general congruent centrally symmetric convex regions in the plane. In all cases we have coloring algorithms that use O(log n) colors (where n is the number of regions). Tightness is demonstrated by showing that even in the case of unit disks, $\\Theta(\\log n)$ colors may be necessary. For rectangles and hexagons we also obtain a constant-ratio approximation algorithm when the ratio between the largest and smallest rectangle (hexagon) is a constant. We also consider a dual problem of CF-coloring points with respect to sets. Given a set system $(X,{\\cal S})$, the goal in the dual problem is to color the elements in X with a minimum number of colors so that every set $S \\in {\\cal S}$ contains a point whose color appears only once in S. We show that O(log |X|) colors suffice for set systems in which X is a set of points in the plane and the sets are intersections of X with scaled translations of a convex region. This result is used in proving that O(log n) colors suffice in the primal version.<\/jats:p>","DOI":"10.1137\/s0097539702431840","type":"journal-article","created":{"date-parts":[[2003,11,17]],"date-time":"2003-11-17T21:00:45Z","timestamp":1069102845000},"page":"94-136","source":"Crossref","is-referenced-by-count":145,"title":["Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks"],"prefix":"10.1137","volume":"33","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zvi","family":"Lotker","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shakhar","family":"Smorodinsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","unstructured":"K. Aardal, S. van Hoesel, A. Koster, C. Mannino, and A. Sassano,\n                      Models and Solutions Techniques for Frequency Assignment Problem\n                      , ZIB Report 01\u201040, Konrad\u2010Zuse\u2010Zentrum f\u00fcr Informationstechnik Berlin, Berlin, Germany, 2001;"},{"key":"R1","unstructured":"available online at http:\/\/www.zib.de\/PaperWeb\/abstracts\/ZR\u201001\u201040\/."},{"key":"R2","unstructured":"Z. Abrams, J. K\u00f6nemann, A. Meyerson, K. Munagala, and S. Plotkin,\n                      Facility Location with Interference\n                      , Working paper 2001\u2010E23, GSTA, Carnegie Mellon University, Pittsburgh, PA, 2001."},{"key":"R3","first-page":"421","volume":"21","author":"Appel K.","year":"1977","journal-title":"Illinois J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0019-2082","issn-type":"print"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1256049012"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90042-H"},{"key":"R6","unstructured":"R. Bar\u2010Yehuda,\n                      personal communication\n                      , Technion, Israel Institute of Technology, Haifa, Israel, 2001."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03427-9"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"R9","volume-title":"Introduction to geometry","author":"Coxeter H.","year":"1969"},{"key":"R10","unstructured":"N. W. Dunkin, J. E. Bater, P. G. Jeavons, and D. A. Cohen,\n                      Towards High Order Constraint Representations for the Frequency Assignment Problem\n                      , Technical report CSD\u2010TR\u201098\u201005, Computer Science Department, Royal Holloway, University of London, London, 1998;"},{"key":"R10","unstructured":"available online at http:\/\/www.dcs.rhbnc.ac.uk\/research\/constraints\/publications\/index.shtml."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"R12","unstructured":"M. Galota, C. Glasser, S. Reith, and H. Vollmer,\n                      A Polynomial\u2010Time Approximation Scheme for Base Station Positioning in UMTS Networks\n                      , Technical report 264, Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, W\u00fcrzburg, Germany, 2000."},{"key":"R13","unstructured":"S. Har\u2010Peled and S. Smorodinsky,\n                      On conflict\u2010free coloring of points and simple regions in the plane\n                      , in Proceedings of the 19th Annual ACM Symposium on Computing Geometry, San Diego, CA, 2003, pp. 114\u2013123."},{"key":"R14","unstructured":"X. Huang,\n                      Automatic Cell Planning for Mobile Network Design: Optimization Models and Algorithms\n                      , Ph.D. dissertation, Universit\u00e4t Karlsruhe, Karlsruhe, Germany, 2001."},{"key":"R15","unstructured":"S. O. Krumke, M. V. Marathe, and S. S. Ravi, Models and approximation algorithms for channel assignment in radio networks, invited paper in Wireless Networks, 7 (2001), pp. 575\u2013584."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230250205"},{"key":"R17","unstructured":"J. Pach and G. T\u00f3th,\n                      Conflict free colorings\n                      , in The Goodman Pollack Festschrift, Algorithms Combin. 25, B. Aronov, S. Basu, J. Pach, and M. Sharir, eds., Springer\u2010Verlag, Berlin, 2003, pp. 665\u2013671."},{"key":"R18","volume-title":"Davenport\u2010Schinzel sequences and their geometric applications","author":"Sharir Micha","year":"1995"},{"key":"R19","unstructured":"S. Smorodinsky,\n                      Combinatorial Problems in Computational Geometry\n                      , Ph.D dissertation, Tel\u2010Aviv University, Tel\u2010Aviv, Israel, 2003."},{"key":"R20","unstructured":"Neil Robertson, Daniel Sanders, Paul Seymour, Robin Thomas, Efficiently four\u2010coloring planar graphs, ACM, New York, 1996, 571\u20135751427555"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539702431840","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:20:06Z","timestamp":1787336406000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539702431840"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["10.1137\/S0097539702431840"],"URL":"https:\/\/doi.org\/10.1137\/s0097539702431840","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}