{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T14:16:54Z","timestamp":1772893014426,"version":"3.50.1"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030364113","type":"print"},{"value":"9783030364120","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-36412-0_49","type":"book-chapter","created":{"date-parts":[[2019,12,5]],"date-time":"2019-12-05T19:04:15Z","timestamp":1575572655000},"page":"601-612","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On Conflict-Free Chromatic Guarding of\u00a0Simple Polygons"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4785-7496","authenticated-orcid":false,"given":"Onur","family":"\u00c7a\u011f\u0131r\u0131c\u0131","sequence":"first","affiliation":[]},{"given":"Subir Kumar","family":"Ghosh","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2125-1514","authenticated-orcid":false,"given":"Petr","family":"Hlin\u011bn\u00fd","sequence":"additional","affiliation":[]},{"given":"Bodhayan","family":"Roy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,23]]},"reference":[{"key":"49_CR1","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10479-007-0178-0","volume":"153","author":"KI Aardal","year":"2007","unstructured":"Aardal, K.I., van Hoesel, S.P.M., Koster, A.M.C.A., Mannino, C., Sassano, A.: Models and solution techniques for frequency assignment problems. Ann. Oper. Res. 153, 79\u2013129 (2007)","journal-title":"Ann. Oper. Res."},{"key":"49_CR2","doi-asserted-by":"crossref","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists $$$$\\mathbb{R}$$-complete. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 65\u201373 (2018)","DOI":"10.1145\/3188745.3188868"},{"key":"49_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3186897","volume":"14","author":"P Ashok","year":"2018","unstructured":"Ashok, P., Fomin, F.V., Kolay, S., Saurabh, S., Zehavi, M.: Exact algorithms for terrain guarding. ACM Trans. Algorithms 14, 1\u201320 (2018)","journal-title":"ACM Trans. Algorithms"},{"key":"49_CR4","doi-asserted-by":"crossref","unstructured":"B\u00e4rtschi, A., Ghosh, S.K., Mihal\u00e1k, M., Tschager, T., Widmayer, P.: Improved bounds for the conflict-free chromatic art gallery problem. In: Proceedings of the 30th Annual Symposium on Computational Geometry, pp. 144\u2013153 (2014)","DOI":"10.1145\/2582112.2582117"},{"key":"49_CR5","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/s00453-012-9732-5","volume":"68","author":"A B\u00e4rtschi","year":"2014","unstructured":"B\u00e4rtschi, A., Suri, S.: Conflict-free chromatic art gallery coverage. Algorithmica 68, 265\u2013283 (2014)","journal-title":"Algorithmica"},{"key":"49_CR6","doi-asserted-by":"publisher","first-page":"1631","DOI":"10.1137\/S0097539704446384","volume":"36","author":"B Ben-Moshe","year":"2007","unstructured":"Ben-Moshe, B., Katz, M.J., Mitchell, J.S.B.: A constant-factor approximation algorithm for optimal 1.5D terrain guarding. SIAM J. Comput. 36, 1631\u20131647 (2007)","journal-title":"SIAM J. Comput."},{"key":"49_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry, Algorithms and Applications","author":"M Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry, Algorithms and Applications, 3rd edn. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-77974-2","edition":"3"},{"key":"49_CR8","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.dam.2016.12.015","volume":"228","author":"P Bhattacharya","year":"2017","unstructured":"Bhattacharya, P., Ghosh, S.K., Roy, B.: Approximability of guarding weak visibility polygons. Discrete Appl. Math. 228, 109\u2013129 (2017)","journal-title":"Discrete Appl. Math."},{"key":"49_CR9","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0095-8956(73)90042-7","volume":"15","author":"N Biggs","year":"1973","unstructured":"Biggs, N.: Perfect codes in graphs. J. Comb. Theory Ser. B 15, 289\u2013296 (1973)","journal-title":"J. Comb. Theory Ser. B"},{"key":"49_CR10","unstructured":"Bonnet, \u00c9., Giannopoulos, P.: Orthogonal terrain guarding is NP-complete. In: 34th International Symposium on Computational Geometry, pp. 1\u201315 (2018)"},{"key":"49_CR11","unstructured":"Bonnet, \u00c9., Miltzow, T.: Parameterized hardness of art gallery problems. In: 24th Annual European Symposium on Algorithms, pp. 1\u201317 (2016)"},{"key":"49_CR12","unstructured":"Bonnet, \u00c9., Miltzow, T.: An approximation algorithm for the art gallery problem. In: 33rd International Symposium on Computational Geometry, pp. 1\u201315 (2017)"},{"key":"49_CR13","doi-asserted-by":"crossref","unstructured":"\u00c7a\u011f\u0131r\u0131c\u0131, O., Ghosh, S., Hlin\u011bn\u00fd, P., Roy, B.: On conflict-free chromatic guarding of simple polygons. arXiv:1904.08624 , June 2019","DOI":"10.1007\/978-3-030-36412-0_49"},{"key":"49_CR14","unstructured":"Chazelle, B.: Approximation and decomposition of shapes. In: Schwartz, J.T. (ed.) Advances in Robotics 1: Algorithmic and Geometric Aspects of Robotics, pp. 145\u2013185 (1987)"},{"key":"49_CR15","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"V Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V.: A combinatorial theorem in plane geometry. J. Comb. Theory 18, 39\u201341 (1975)","journal-title":"J. Comb. Theory"},{"key":"49_CR16","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/j.ipl.2006.05.014","volume":"100","author":"A Efrat","year":"2006","unstructured":"Efrat, A., Har-Peled, S.: Guarding galleries and terrains. Inf. Process. Lett. 100, 238\u2013245 (2006)","journal-title":"Inf. Process. Lett."},{"key":"49_CR17","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00453-001-0040-8","volume":"31","author":"S Eidenbenz","year":"2001","unstructured":"Eidenbenz, S., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica 31, 79\u2013113 (2001)","journal-title":"Algorithmica"},{"key":"49_CR18","doi-asserted-by":"crossref","unstructured":"Erickson, L.H., LaValle, S.M.: An art gallery approach to ensuring that landmarks are distinguishable. In: Robotics: Science and Systems VII (2011)","DOI":"10.15607\/RSS.2011.VII.011"},{"key":"49_CR19","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/j.dam.2009.12.004","volume":"158","author":"SK Ghosh","year":"2010","unstructured":"Ghosh, S.K.: Approximation algorithms for art gallery problems in polygons. Discrete Appl. Math. 158, 718\u2013722 (2010)","journal-title":"Discrete Appl. Math."},{"key":"49_CR20","doi-asserted-by":"publisher","first-page":"1120","DOI":"10.1137\/S0097539792233257","volume":"26","author":"LJ Guibas","year":"1997","unstructured":"Guibas, L.J., Motwani, R., Raghavan, P.: The robot localization problem. SIAM J. Comput. 26, 1120\u20131138 (1997)","journal-title":"SIAM J. Comput."},{"key":"49_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-3585-4","volume-title":"Unsolved Problems in Number Theory","author":"RK Guy","year":"1994","unstructured":"Guy, R.K.: Unsolved Problems in Number Theory. Springer, New York (1994). https:\/\/doi.org\/10.1007\/978-1-4899-3585-4"},{"key":"49_CR22","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.comgeo.2018.01.003","volume":"73","author":"F Hoffmann","year":"2018","unstructured":"Hoffmann, F., Kriegel, K., Suri, S., Verbeek, K., Willert, M.: Tight bounds for conflict-free chromatic guarding of orthogonal art galleries. Comput. Geom. 73, 24\u201334 (2018)","journal-title":"Comput. Geom."},{"key":"49_CR23","unstructured":"Katz, M.J.: A PTAS for vertex guarding weakly-visible polygons - an extended abstract. CoRR abs\/1803.02160 (2018)"},{"key":"49_CR24","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1142\/S0218195911003639","volume":"21","author":"MJ Katz","year":"2011","unstructured":"Katz, M.J., Morgenstern, G.: Guarding orthogonal art galleries with sliding cameras. Int. J. Comput. Geom. Appl. 21, 241\u2013250 (2011)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"49_CR25","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/s00454-011-9352-x","volume":"46","author":"J King","year":"2011","unstructured":"King, J., Kirkpatrick, D.G.: Improved approximation for guarding simple galleries from the perimeter. Discrete Comput. Geom. 46, 252\u2013269 (2011)","journal-title":"Discrete Comput. Geom."},{"key":"49_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/BFb0017162","volume-title":"Mathematical Foundations of Computer Science 1988","author":"J Kratochv\u00edl","year":"1988","unstructured":"Kratochv\u00edl, J., K\u0159iv\u00e1nek, M.: On the computational complexity of codes in graphs. In: Chytil, M.P., Koubek, V., Janiga, L. (eds.) MFCS 1988. LNCS, vol. 324, pp. 396\u2013404. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/BFb0017162"},{"key":"49_CR27","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"32","author":"DT Lee","year":"1986","unstructured":"Lee, D.T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Inf. Theory 32, 276\u2013282 (1986)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"49_CR28","volume-title":"Art Gallery Theorems and Algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, Oxford (1987)"},{"key":"49_CR29","series-title":"Bolyai Society Mathematical Studies","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-642-41498-5_12","volume-title":"Geometry \u2014 Intuitive, Discrete, and Convex","author":"S Smorodinsky","year":"2013","unstructured":"Smorodinsky, S.: Conflict-free coloring and its applications. In: B\u00e1r\u00e1ny, I., B\u00f6r\u00f6czky, K.J., T\u00f3th, G.F., Pach, J. (eds.) Geometry \u2014 Intuitive, Discrete, and Convex. BSMS, vol. 24, pp. 331\u2013389. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-41498-5_12"},{"key":"49_CR30","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1109\/70.88124","volume":"6","author":"S Suri","year":"1990","unstructured":"Suri, S.: On some link distance problems in a simple polygon. IEEE J. Robot. Autom. 6, 108\u2013113 (1990)","journal-title":"IEEE J. Robot. Autom."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-36412-0_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,14]],"date-time":"2019-12-14T03:57:57Z","timestamp":1576295877000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-36412-0_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030364113","9783030364120"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-36412-0_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"23 November 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Xiamen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 December 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoaconference.org\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"108","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"45% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.2","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}