{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:44:48Z","timestamp":1760143488745,"version":"build-2065373602"},"reference-count":18,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2024,2,9]],"date-time":"2024-02-09T00:00:00Z","timestamp":1707436800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea (NRF)","doi-asserted-by":"publisher","award":["RS-2023-00219980","2022R1F1A107586911","2017-0-00905","2019-0-01906"],"award-info":[{"award-number":["RS-2023-00219980","2022R1F1A107586911","2017-0-00905","2019-0-01906"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100014188","name":"Institute of Information &amp; communications Technology Planning &amp; Evaluation(IITP)","doi-asserted-by":"publisher","award":["RS-2023-00219980","2022R1F1A107586911","2017-0-00905","2019-0-01906"],"award-info":[{"award-number":["RS-2023-00219980","2022R1F1A107586911","2017-0-00905","2019-0-01906"]}],"id":[{"id":"10.13039\/501100014188","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Software Star Lab","award":["RS-2023-00219980","2022R1F1A107586911","2017-0-00905","2019-0-01906"],"award-info":[{"award-number":["RS-2023-00219980","2022R1F1A107586911","2017-0-00905","2019-0-01906"]}]},{"DOI":"10.13039\/501100014188","name":"Artificial Intelligence Graduate School Program(POSTECH))","doi-asserted-by":"publisher","award":["RS-2023-00219980","2022R1F1A107586911","2017-0-00905","2019-0-01906"],"award-info":[{"award-number":["RS-2023-00219980","2022R1F1A107586911","2017-0-00905","2019-0-01906"]}],"id":[{"id":"10.13039\/501100014188","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Given a set of n disks in the plane, we study the problem of finding k lines that together intersect the maximum number of input disks. We consider three variants of this problem with the following constraints on the solution: (1) no constraint on the lines, (2) the k lines should be parallel and (3) the k lines should pass through a common point. For k=2, we give O(n3logn)-time algorithms for all three cases. For any fixed k\u22653, we give an O(n3k\/2)-time algorithm for (1). For variants (2) and (3), the running times of our algorithms vary from O(n4) to O(n6).<\/jats:p>","DOI":"10.3390\/sym16020206","type":"journal-article","created":{"date-parts":[[2024,2,9]],"date-time":"2024-02-09T03:53:46Z","timestamp":1707450826000},"page":"206","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximum Coverage by k Lines"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-3363-2406","authenticated-orcid":false,"given":"Chaeyoon","family":"Chung","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang 37673, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3586-3431","authenticated-orcid":false,"given":"Antoine","family":"Vigneron","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Ulsan National Institute of Science and Technology, Ulsan 44919, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7177-1679","authenticated-orcid":false,"given":"Hee-Kap","family":"Ahn","sequence":"additional","affiliation":[{"name":"Graduate School of Artificial Intelligence, Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang 37673, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,2,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/j.comgeo.2011.11.006","article-title":"On a class of O(n2) problems in computational geometry","volume":"45","author":"Gajentaan","year":"2012","journal-title":"Comput. Geom. Theory Appl."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.ipl.2016.11.001","article-title":"Refined algorithms for hitting many intervals","volume":"118","author":"Damaschke","year":"2017","journal-title":"Inf. Process. Lett."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1051\/ro\/1997310100451","article-title":"The disjoint cliques problem","volume":"31","author":"Jansen","year":"1997","journal-title":"RAIRO Rech. Op\u00c9rationnelle"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/s10951-021-00691-w","article-title":"Scheduling with gaps: New models and algorithms","volume":"24","author":"Chrobak","year":"2021","journal-title":"J. Sched."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1016\/j.comgeo.2015.06.006","article-title":"On the approximability of covering points by lines and related problems","volume":"48","author":"Dumitrescu","year":"2015","journal-title":"Comput. Geom."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1002\/(SICI)1520-6750(199809)45:6<615::AID-NAV5>3.0.CO;2-5","article-title":"Analysis of the greedy approach in problems of maximum k-coverage","volume":"45","author":"Hochbaum","year":"1998","journal-title":"Nav. Res. Logist."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.tcs.2017.11.026","article-title":"Near-linear time approximation schemes for geometric maximum coverage","volume":"725","author":"Jin","year":"2018","journal-title":"Theor. Comput. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.comgeo.2015.12.003","article-title":"Geometric permutations of non-overlapping unit balls revisited","volume":"53","author":"Ha","year":"2016","journal-title":"Comput. Geom."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"4173","DOI":"10.1016\/j.tcs.2011.01.039","article-title":"The directed Hausdorff distance between imprecise point sets","volume":"412","author":"Knauer","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1016\/j.comgeo.2008.12.007","article-title":"Delaunay triangulation of imprecise points in linear time after preprocessing","volume":"43","author":"Snoeyink","year":"2010","journal-title":"Comput. Geom. Theory Appl."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1142\/S0218195912600023","article-title":"Computing the Discrete Fr\u00e9chet distance with imprecise input","volume":"22","author":"Ahn","year":"2012","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"ref_12","first-page":"537","article-title":"Edge detection techniques\u2014An overview","volume":"8","author":"Ziou","year":"1998","journal-title":"Pattern Recognit. Image Anal. C\/C Raspoznavaniye Obraz. I Anal. Izobr."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Goldberg, A.V., and Zhou, Y. (2009). Algorithmic Aspects in Information and Management, Springer.","DOI":"10.1007\/978-3-642-02158-9"},{"key":"ref_14","first-page":"284","article-title":"Can the Measure of \u22c31n[ai,bi] be Computed in Less Than O(nlogn) Steps?","volume":"84","author":"Klee","year":"1977","journal-title":"Am. Math. Mon."},{"key":"ref_15","unstructured":"Berg, M.d., Cheong, O., Kreveld, M.v., and Overmars, M. (2008). Computational Geometry: Algorithms and Applications, Springer. [3rd ed.]."},{"key":"ref_16","unstructured":"Amato, N., Goodrich, M., and Ramos, E. (2000, January 9\u201311). Computing the arrangement of curve segments: Divide-and-conquer algorithms via sampling. Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Chan, T.M. (2013, January 26\u201329). Klee\u2019s Measure Problem Made Easy. Proceedings of the 54th Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2013.51"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/0196-6774(83)90012-3","article-title":"Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane","volume":"4","author":"Imai","year":"1983","journal-title":"J. Algorithms"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/16\/2\/206\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T13:57:42Z","timestamp":1760104662000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/16\/2\/206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,9]]},"references-count":18,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2024,2]]}},"alternative-id":["sym16020206"],"URL":"https:\/\/doi.org\/10.3390\/sym16020206","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2024,2,9]]}}}