{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:31Z","timestamp":1759638031262,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030752415"},{"type":"electronic","value":"9783030752422"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-75242-2_20","type":"book-chapter","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T15:22:29Z","timestamp":1620141749000},"page":"286-299","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Covering a Set of Line Segments with a Few Squares"],"prefix":"10.1007","author":[{"given":"Joachim","family":"Gudmundsson","sequence":"first","affiliation":[]},{"given":"Mees","family":"van de Kerkhof","sequence":"additional","affiliation":[]},{"given":"Andr\u00e9","family":"van Renssen","sequence":"additional","affiliation":[]},{"given":"Frank","family":"Staals","sequence":"additional","affiliation":[]},{"given":"Lionov","family":"Wiratma","sequence":"additional","affiliation":[]},{"given":"Sampson","family":"Wong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,4]]},"reference":[{"issue":"2","key":"20_CR1","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s00453-001-0110-y","volume":"33","author":"PK Agarwal","year":"2002","unstructured":"Agarwal, P.K., Procopiuc, C.M.: Exact and approximation algorithms for clustering. Algorithmica 33(2), 201\u2013226 (2002)","journal-title":"Algorithmica"},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.tcs.2015.11.029","volume":"729","author":"S Bereg","year":"2018","unstructured":"Bereg, S., et al.: Optimizing squares covering a set of points. Theor. Comput. Sci. 729, 68\u201383 (2018)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Damiani, M.L., Issa, H., Cagnacci, F.: Extracting stay regions with uncertain boundaries from GPS trajectories: a case study in animal ecology. In: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 253\u2013262 (2014)","DOI":"10.1145\/2666310.2666417"},{"issue":"2","key":"20_CR4","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1002\/1520-6750(198704)34:2<229::AID-NAV3220340207>3.0.CO;2-1","volume":"34","author":"Z Drezner","year":"1987","unstructured":"Drezner, Z.: On the rectangular $$p$$-center problem. Naval Res. Logistics (NRL) 34(2), 229\u2013234 (1987)","journal-title":"Naval Res. Logistics (NRL)"},{"issue":"3","key":"20_CR5","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"RJ Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12(3), 133\u2013137 (1981)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"20_CR6","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/3054132","volume":"50","author":"J Gudmundsson","year":"2017","unstructured":"Gudmundsson, J., Horton, M.: Spatio-temporal analysis of team sports. ACM Comput. Surv. (CSUR) 50(2), 22 (2017)","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Gudmundsson, J., van de Kerkhof, M., Renssen, A., Staals, F., Wiratma, L., Wong, S.: Covering a set of line segments with a few squares. CoRR, abs\/2101.09913 (2021)","DOI":"10.1007\/978-3-030-75242-2_20"},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Gudmundsson, J., van Kreveld, M., Staals, F.: Algorithms for hotspot computation on trajectory data. In: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 134\u2013143 (2013)","DOI":"10.1145\/2525314.2525359"},{"key":"20_CR9","unstructured":"Hoffmann, M.: Covering polygons with few rectangles. In: Abstracts 17th European Workshop Computational Geometry, pp. 39\u201342 (2001)"},{"issue":"1","key":"20_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01185335","volume":"9","author":"RZ Hwang","year":"1993","unstructured":"Hwang, R.Z., Lee, R.C.T., Chang, R.C.: The slab dividing approach to solve the Euclidean $$p$$-center problem. Algorithmica 9(1), 1\u201322 (1993)","journal-title":"Algorithmica"},{"issue":"1","key":"20_CR11","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N., Supowit, K.J.: On the complexity of some common geometric location problems. SIAM J. Comput. 13(1), 182\u2013196 (1984)","journal-title":"SIAM J. Comput."},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Nussbaum, D.: Rectilinear $$p$$-piercing problems. In: Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC, pp. 316\u2013323 (1997)","DOI":"10.1145\/258726.258828"},{"key":"20_CR13","unstructured":"Mahapatra, P.R.S., Goswami, P.P., Das, S.: Maximal covering by two isothetic unit squares. In: Canadian Conference on Computational Geometry, pp. 103\u2013106 (2008)"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.tcs.2018.10.013","volume":"769","author":"S Sadhu","year":"2019","unstructured":"Sadhu, S., Roy, S., Nandy, S.C., Roy, S.: Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares. Theor. Comput. Sci. 769, 63\u201374 (2019)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"20_CR15","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1142\/S0218195999000157","volume":"9","author":"M Segal","year":"1999","unstructured":"Segal, M.: On piercing sets of axis-parallel rectangles and rings. Int. J. Comput. Geometry Appl. 9(3), 219\u2013234 (1999)","journal-title":"Int. J. Comput. Geometry Appl."},{"key":"20_CR16","volume-title":"Davenport-Schinzel Sequences and their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and their Geometric Applications. Cambridge University Press, Cambridge (1995)"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Sharir, M., Welzl, E.: Rectilinear and polygonal p-piercing and p-center problems. In: Proceedings of the 12th Annual Symposium on Computational Geometry, pp. 122\u2013132 (1996)","DOI":"10.1145\/237218.237255"},{"key":"20_CR18","first-page":"615","volume":"1","author":"A Stohl","year":"2002","unstructured":"Stohl, A.: Computation, accuracy and applications of trajectories\u2013a review and bibliography. Dev. Environ. Sci. 1, 615\u2013654 (2002)","journal-title":"Dev. Environ. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-75242-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T09:47:50Z","timestamp":1672048070000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-75242-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030752415","9783030752422"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-75242-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"4 May 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 May 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 May 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/easyconferences.eu\/ciac2021\/","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":"78","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":"27","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":"35% - 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","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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the Corona pandemic the conference was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}