{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T17:30:00Z","timestamp":1768325400444,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540343752","type":"print"},{"value":"9783540343783","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11758471_4","type":"book-chapter","created":{"date-parts":[[2006,6,2]],"date-time":"2006-06-02T06:34:15Z","timestamp":1149230055000},"page":"6-17","source":"Crossref","is-referenced-by-count":13,"title":["Covering a Set of Points with a Minimum Number of Lines"],"prefix":"10.1007","author":[{"given":"Magdalene","family":"Grantson","sequence":"first","affiliation":[]},{"given":"Christos","family":"Levcopoulos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","first-page":"80","volume-title":"Proc. 15th Ann. ACM Symp. on Theory of Comp.","author":"M. Ben-Or","year":"1983","unstructured":"Ben-Or, M.: Lower Bounds for Algebraic Computation Trees. In: Proc. 15th Ann. ACM Symp. on Theory of Comp., pp. 80\u201386. ACM Press, New York (1983)"},{"key":"#cr-split#-4_CR2.1","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H., Guibas, L., Stolfi, J.: Optimal Point Location in a Monotone Subdivision. SIAM J. Comput.??15, 317???340 (1986);","DOI":"10.1137\/0215023"},{"key":"#cr-split#-4_CR2.2","unstructured":"Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1986)"},{"key":"4_CR3","unstructured":"Grantson, M., Levcopoulos, C.: Covering a Set of Points with a Minimum Number of Lines. Technical Report LU-CS-TR:2005-236, ISSN 1650-1276 Report 156, Also at: http:\/\/www.cs.lth.se\/home\/Magdalene_Grantson\/line.pdf"},{"key":"4_CR4","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0925-7721(95)00020-8","volume":"6","author":"L. Guibas","year":"1996","unstructured":"Guibas, L., Overmars, M., Robert, J.: The Exact Fitting Problem in Higher Dimensions. Computational Geometry: Theory and Applications\u00a06, 215\u2013230 (1996)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. Johnson","year":"1974","unstructured":"Johnson, D.: Approximation Algorithms for Combinatorial Problems. J. of Comp. Syst. Sci.\u00a09, 256\u2013278 (1974)","journal-title":"J. of Comp. Syst. Sci."},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"624","DOI":"10.1007\/3-540-45022-X_53","volume-title":"Automata, Languages and Programming","author":"V. Kumar","year":"2000","unstructured":"Kumar, V., Arya, S., Ramesh, H.: Hardness of Set Cover With Intersection\u00a01. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 624\u2013635. Springer, Heidelberg (2000)"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/3-540-45749-6_58","volume-title":"Algorithms - ESA 2002","author":"S. Langerman","year":"2002","unstructured":"Langerman, S., Morin, P.: Covering Things with Things. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 662\u2013673. Springer, Heidelberg (2002)"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/0167-6377(82)90039-6","volume":"1","author":"N. Megiddo","year":"1982","unstructured":"Megiddo, N., Tamir, A.: On the Complexity of Locating Linear Facilities in the Plane. Operation Research Letters\u00a01, 194\u2013197 (1982)","journal-title":"Operation Research Letters"},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"Sarnak, N., Tarjan, R.E.: Planar Point Location Using Persistent Search Tree. Comm.\u00a0ACM\u00a029, 669\u2013679 (1986)","journal-title":"Comm.\u00a0ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11758471_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:04:30Z","timestamp":1619492670000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11758471_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540343752","9783540343783"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/11758471_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}