{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T06:15:50Z","timestamp":1757571350380,"version":"3.30.1"},"reference-count":27,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2001,7,1]],"date-time":"2001-07-01T00:00:00Z","timestamp":993945600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4399,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2001,7]]},"DOI":"10.1016\/s0304-3975(00)00227-9","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T10:59:17Z","timestamp":1027594757000},"page":"17-29","source":"Crossref","is-referenced-by-count":5,"title":["On point covers of c-oriented polygons"],"prefix":"10.1016","volume":"263","author":[{"given":"Frank","family":"Nielsen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(00)00227-9_BIB1","unstructured":"P.K. Agarwal, Mark van Kreyeld, S. Suri, Label placement by maximum independent set in rectangles, Proc. 9th Canad. Conf. on Computational Geometry, 1997, pp. 233\u2013238."},{"year":"1993","series-title":"Parallel Computational Geometry","author":"Akl","key":"10.1016\/S0304-3975(00)00227-9_BIB2"},{"key":"10.1016\/S0304-3975(00)00227-9_BIB3","doi-asserted-by":"crossref","unstructured":"S. Arora, D. Karger, M. Karpinski, Polynomial-time approximation schemes for dense instances of NP-hard problems. Symp. on Theory of Computing, 1995, pp. 284\u2013293.","DOI":"10.1145\/225058.225140"},{"key":"10.1016\/S0304-3975(00)00227-9_BIB4","doi-asserted-by":"crossref","unstructured":"M. Bellare, M. Sudan, Improved non-approximability results. Proc. 26th Annu. ACM Symp. on Theory of Computing, 1994, pp. 184\u2013193.","DOI":"10.1145\/195058.195129"},{"key":"10.1016\/S0304-3975(00)00227-9_BIB5","doi-asserted-by":"crossref","unstructured":"H. Br\u00f6nnimann, M.T. Goodrich, Almost optimal set covers in finite VC-dimension, Proc. 10th Annu. ACM Symp. on Computational Geometry, 1994, pp. 293\u2013302.","DOI":"10.1145\/177424.178029"},{"key":"10.1016\/S0304-3975(00)00227-9_BIB6","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","article-title":"A greedy heuristic for the set-covering problem","volume":"4","author":"Chv\u00e1tal","year":"1979","journal-title":"Math. Oper. Res."},{"issue":"1","key":"10.1016\/S0304-3975(00)00227-9_BIB7","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF01305948","article-title":"Bounding the vertex cover number of a hypergraph","volume":"14","author":"Ding","year":"1994","journal-title":"Combinatorica"},{"key":"10.1016\/S0304-3975(00)00227-9_BIB8","unstructured":"S. Doddi, M. Marathe, A. Mirzaian, B. Moret, B. Zhu, Map labeling and its generalization, Proc. 8th ACM-SIAM Symp. on Discrete Algorithms, 1997, pp. 148\u2013157."},{"key":"10.1016\/S0304-3975(00)00227-9_BIB9","doi-asserted-by":"crossref","unstructured":"R.-chii Duh, M. F\u00fcrer, Approximation of k-set cover by semi-local optimization, Proc. 29th Annu. ACM Symp. on Theory of Computing, 1997, pp. 256\u2013264.","DOI":"10.1145\/258533.258599"},{"key":"10.1016\/S0304-3975(00)00227-9_BIB10","series-title":"Dynamic data structures for fat objects and their applications, Proc. Work. Alg. Data Struct. 97, Halifax, Nova Scotia, Canada, Lecture Notes in Computer Science","first-page":"297","author":"Efrat","year":"1997"},{"key":"10.1016\/S0304-3975(00)00227-9_BIB11","doi-asserted-by":"crossref","unstructured":"U. Feige, A threshold of lnn for approximating set cover (preliminary version), Proc. 28th Annu. ACM Symp. on Theory of Computing, Philadelphia, Pennsylvania, 22\u201324 May, 1996, pp. 314\u2013318.","DOI":"10.1145\/237814.237977"},{"key":"10.1016\/S0304-3975(00)00227-9_BIB12","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0012-365X(93)90587-J","article-title":"Covering boxes by points","volume":"120","author":"Fon der Flass","year":"1993","journal-title":"Discrete Math."},{"issue":"3","key":"10.1016\/S0304-3975(00)00227-9_BIB13","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","article-title":"Optimal packing and covering in the plane are NP-complete","volume":"12","author":"Fowler","year":"1981","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(00)00227-9_BIB14","first-page":"155","article-title":"On intersections of similar sets","volume":"18","author":"Gr\u00fcnbaum","year":"1959","journal-title":"Portugal Math."},{"issue":"3","key":"10.1016\/S0304-3975(00)00227-9_BIB15","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1137\/0211045","article-title":"Approximation algorithms of the set covering and vertex cover problems","volume":"11","author":"Hochbaum","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(00)00227-9_BIB16","first-page":"130","article-title":"Approximations schemes for covering and packing problems in image processing and VLSI","volume":"31","author":"Hochbaum","year":"1984","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(00)00227-9_BIB17","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0196-6774(87)90012-5","article-title":"Fast approximation algorithms for a nonconvex covering problem","volume":"8","author":"Hochbaum","year":"1987","journal-title":"J. Algorithms"},{"issue":"2","key":"10.1016\/S0304-3975(00)00227-9_BIB18","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02280661","article-title":"On point covers of parallel rectangles","volume":"23","author":"K\u00e1rolyi","year":"1991","journal-title":"Period. Math. Hungar."},{"key":"10.1016\/S0304-3975(00)00227-9_BIB19","unstructured":"G. K\u00e1rolyi, G. Tardos, On point covers of multiples intervals and axis-parallel rectangles, Technical Report, DIMACS TR 95-45, 1995."},{"key":"10.1016\/S0304-3975(00)00227-9_BIB20","unstructured":"M. Karpinski, A. Zelikovsky, Approximating dense cases of covering problems, Technical Report, DIMACS TR 96-59, 1996."},{"key":"10.1016\/S0304-3975(00)00227-9_BIB21","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/S0925-7721(96)00027-2","article-title":"3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects","volume":"8","author":"Katz","year":"1997","journal-title":"Comput. Geom. Theory Appl."},{"key":"10.1016\/S0304-3975(00)00227-9_BIB22","doi-asserted-by":"crossref","unstructured":"M.J. Katz, F. Nielsen, On piercing sets of objects, Proc. 12th Annu. ACM Symp. on Computational Geometry, 1996, pp. 113\u2013121.","DOI":"10.1145\/237218.237253"},{"key":"10.1016\/S0304-3975(00)00227-9_BIB23","doi-asserted-by":"crossref","unstructured":"F. Nielsen, Fast stabbing of boxes in high dimensions. Proc. 8th Canad. Conf. on Computational Geometry, 1996, pp. 87\u201392.","DOI":"10.1515\/9780773591134-017"},{"key":"10.1016\/S0304-3975(00)00227-9_BIB24","doi-asserted-by":"crossref","unstructured":"C. Poon, B. Zhu, F. Chin, A polynomial time solution for labeling a rectilinear map. Proc. 13th Annu. ACM Symp. on Computational Geometry, 1997, pp. 451\u2013453.","DOI":"10.1145\/262839.263079"},{"year":"1985","series-title":"Computational Geometry: An Introduction.","author":"Preparata","key":"10.1016\/S0304-3975(00)00227-9_BIB25"},{"key":"10.1016\/S0304-3975(00)00227-9_BIB26","doi-asserted-by":"crossref","unstructured":"P. Slav\u0131\u0301k, A tight analysis of the greedy algorithm for set cover, Proc. 28th ACM Symp. on Theory of Computing, 1996.","DOI":"10.1145\/237814.237991"},{"key":"10.1016\/S0304-3975(00)00227-9_BIB27","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/S0925-7721(96)00007-7","article-title":"A practical map labeling algorithm","volume":"7","author":"Wagner","year":"1997","journal-title":"Comput. Geom. Theory Appl."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500002279?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500002279?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T17:33:16Z","timestamp":1733247196000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397500002279"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,7]]},"references-count":27,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,7]]}},"alternative-id":["S0304397500002279"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(00)00227-9","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[2001,7]]}}}