{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T11:00:29Z","timestamp":1648638029766},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2019,3]]},"abstract":"<jats:p> We introduce the fully-dynamic conflict-free coloring problem for a set\u00a0[Formula: see text] of intervals in [Formula: see text] with respect to points, where the goal is to maintain a conflict-free coloring for\u00a0[Formula: see text] under insertions and deletions. A coloring is conflict-free if for each point [Formula: see text] contained in some interval, [Formula: see text] is contained in an interval whose color is not shared with any other interval containing [Formula: see text]. We investigate trade-offs between the number of colors used and the number of intervals that are recolored upon insertion or deletion of an interval. Our results include: <\/jats:p><jats:p> a lower bound on the number of recolorings as a function of the number of colors, which implies that with [Formula: see text] recolorings per update the worst-case number of colors is [Formula: see text], and that any strategy using [Formula: see text] colors needs [Formula: see text] recolorings; a coloring strategy that uses [Formula: see text] colors at the cost of [Formula: see text] recolorings, and another strategy that uses [Formula: see text] colors at the cost of [Formula: see text] recolorings; stronger upper and lower bounds for special cases. <\/jats:p><jats:p> We also consider the kinetic setting where the intervals move continuously (but there are no insertions or deletions); here we show how to maintain a coloring with only four colors at the cost of three recolorings per event and show this is tight. <\/jats:p>","DOI":"10.1142\/s021819591940003x","type":"journal-article","created":{"date-parts":[[2019,8,20]],"date-time":"2019-08-20T07:31:31Z","timestamp":1566286291000},"page":"49-72","source":"Crossref","is-referenced-by-count":0,"title":["Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points"],"prefix":"10.1142","volume":"29","author":[{"given":"Mark","family":"de Berg","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, 5600 MB Eindhoven, the Netherlands"}]},{"given":"Tim","family":"Leijsen","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, 5600 MB Eindhoven, the Netherlands"}]},{"given":"Aleksandar","family":"Markovic","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, 5600 MB Eindhoven, the Netherlands"}]},{"given":"Andr\u00e9","family":"van Renssen","sequence":"additional","affiliation":[{"name":"University of Sydney, NSW 2006, Australia"}]},{"given":"Marcel","family":"Roeloffzen","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands"}]},{"given":"Gerhard","family":"Woeginger","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, 52062 Aachen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2019,8,20]]},"reference":[{"issue":"6","key":"S021819591940003XBIB001","first-page":"2138","volume":"21","author":"Abam M. A.","year":"2014","journal-title":"Scientia Iranica"},{"key":"S021819591940003XBIB002","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990587"},{"key":"S021819591940003XBIB003","doi-asserted-by":"publisher","DOI":"10.1145\/1383369.1383375"},{"key":"S021819591940003XBIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21840-3_9"},{"key":"S021819591940003XBIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"S021819591940003XBIB006","volume-title":"CoRR","author":"de Berg M.","year":"2016"},{"key":"S021819591940003XBIB007","first-page":"27:1","volume-title":"Proc. 28th Int. Symp. Algorithms and Computation, ISAAC 2017","author":"de Berg M.","year":"2017"},{"key":"S021819591940003XBIB008","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9929-x"},{"key":"S021819591940003XBIB009","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137865"},{"key":"S021819591940003XBIB010","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","edition":"3"},{"key":"S021819591940003XBIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_264"},{"key":"S021819591940003XBIB012","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702431840"},{"key":"S021819591940003XBIB013","first-page":"545","volume-title":"Proc. 16th ACM-SIAM Symp. Discrete Algorithms, SODA 2005","author":"Fiat A.","year":"2005"},{"key":"S021819591940003XBIB014","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-005-1162-6"},{"key":"S021819591940003XBIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13731-0_11"},{"issue":"143","key":"S021819591940003XBIB016","first-page":"98","volume":"33","author":"Kierstead H. A.","year":"1981","journal-title":"Congressus Numerantium"},{"key":"S021819591940003XBIB018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41498-5_12"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021819591940003X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,20]],"date-time":"2019-08-20T07:31:39Z","timestamp":1566286299000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021819591940003X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3]]},"references-count":17,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2019,8,20]]},"published-print":{"date-parts":[[2019,3]]}},"alternative-id":["10.1142\/S021819591940003X"],"URL":"https:\/\/doi.org\/10.1142\/s021819591940003x","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3]]}}}