{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T22:13:19Z","timestamp":1766441599641,"version":"3.30.1"},"reference-count":38,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2000,9,1]],"date-time":"2000-09-01T00:00:00Z","timestamp":967766400000},"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":4702,"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":[[2000,9]]},"DOI":"10.1016\/s0304-3975(98)00336-3","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T14:13:43Z","timestamp":1027606423000},"page":"53-72","source":"Crossref","is-referenced-by-count":34,"title":["Fast stabbing of boxes in high dimensions"],"prefix":"10.1016","volume":"246","author":[{"given":"Frank","family":"Nielsen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(98)00336-3_BIB1","unstructured":"P.K. Agarwal, M. van Kreveld, S. Suri, Label placement by maximum independent set in rectangles, Proc. 9th Canad. Conf. Comput. Geom., 1997, pp. 233\u2013238."},{"year":"1993","series-title":"Parallel Computational Geometry","author":"Akl","key":"10.1016\/S0304-3975(98)00336-3_BIB2"},{"key":"10.1016\/S0304-3975(98)00336-3_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 Comp., 1995, pp. 284\u2013293.","DOI":"10.1145\/225058.225140"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB4","unstructured":"E. Assa, M.J. Katz, p-piercing sets of boxes and polytopes, Personal communication, 1998."},{"key":"10.1016\/S0304-3975(98)00336-3_BIB5","doi-asserted-by":"crossref","unstructured":"M. Bellare, M. Sudan, Improved non-approximability results, Proc. 26th Annu. ACM Symp. Theory Comput., 1994, pp. 184\u2013193.","DOI":"10.1145\/195058.195129"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB6","article-title":"Time bounds for selection","volume":"7","author":"Blum","year":"1972","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/S0304-3975(98)00336-3_BIB7","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02570718","article-title":"Almost optimal set covers in finite VC-dimension","volume":"14","author":"Br\u00f6nnimann","year":"1995","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/S0304-3975(98)00336-3_BIB8","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":"3","key":"10.1016\/S0304-3975(98)00336-3_BIB9","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/BF02579232","article-title":"Intersection properties of boxes in Rd","volume":"2","author":"Danzer","year":"1982","journal-title":"Combinatorica"},{"issue":"1","key":"10.1016\/S0304-3975(98)00336-3_BIB10","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(98)00336-3_BIB11","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. Theory Comput., 1997, pp. 256\u2013264.","DOI":"10.1145\/258533.258599"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB12","doi-asserted-by":"crossref","unstructured":"A. Efrat, M.J. Katz, F. Nielsen, M. Sharir, Dynamic data structures for fat objects and their applications, Proc. Work. on Alg. and Data Struct. 97, LNCS 1272, Halifax, Nova Scotia, Canada, 1997, pp. 297\u2013306.","DOI":"10.1007\/3-540-63307-3_69"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB13","doi-asserted-by":"crossref","unstructured":"U. Feige, A threshold of ln n for approximating set cover (preliminary version), Proc. 28th Annual ACM Symp. on the Theory of Computing, Philadelphia, Pennsylvania, 22\u201324 May 1996, pp. 314\u2013318.","DOI":"10.1145\/237814.237977"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB14","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(98)00336-3_BIB15","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."},{"year":"1979","series-title":"Computers and Intractability","author":"Garey","key":"10.1016\/S0304-3975(98)00336-3_BIB16"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB17","unstructured":"P.M. Gruber, J.M. Wills (Eds.), Handbook of Convex Geometry, vol. A, North-Holland, Amsterdam, Netherlands, 1993."},{"key":"10.1016\/S0304-3975(98)00336-3_BIB18","unstructured":"H. Hadwiger, H. Debrunner, Kombinatorische Geometrie in der Ebene. Monographies de l'Enseignement Math\u00e9matique, N2, Geneva, 1960."},{"issue":"3","key":"10.1016\/S0304-3975(98)00336-3_BIB19","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(98)00336-3_BIB20","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(98)00336-3_BIB21","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"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01185335","article-title":"The slab dividing approach to solve the Euclidean p-center problem","volume":"9","author":"Hwang","year":"1993","journal-title":"Algorithmica"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB23","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"},{"issue":"2","key":"10.1016\/S0304-3975(98)00336-3_BIB24","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":"Periodica Mathematica Hungarica"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB25","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(98)00336-3_BIB26","unstructured":"M. Karpinski, A. Zelikovsky, Approximating dense cases of covering problems, Technical report, DIMACS TR 96-59, 1996."},{"key":"10.1016\/S0304-3975(98)00336-3_BIB27","doi-asserted-by":"crossref","unstructured":"M.J. Katz, F. Nielsen, On piercing sets of objects, Proc. 12th Annu. ACM Symp. Comput. Geom., 1996, pp. 113\u2013121.","DOI":"10.1145\/237218.237253"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB28","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0215021","article-title":"The ultimate planar convex hull algorithm?","volume":"15","author":"Kirkpatrick","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(98)00336-3_BIB29","unstructured":"C. Makris, A. Tsakalidis, Fast piercing of iso-oriented rectangles, Proc. 9th Canad. Conf. Comput. Geom., 1997, pp. 217\u2013222."},{"key":"10.1016\/S0304-3975(98)00336-3_BIB30","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek, Approximations and optimal geometric divide-and-conquer, Proc. 23rd Annu. ACM Symp. Theory Comput., 1991, pp. 505\u2013511. Also in J. Comput. Systems Sci. (50)2 (1995) 203\u2013208.","DOI":"10.1006\/jcss.1995.1018"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB31","doi-asserted-by":"crossref","unstructured":"F. Nielsen, Fast stabbing of boxes in high dimensions, Proc. 8th Canad. Conf. Comput. Geom., 1996, pp. 87\u201392.","DOI":"10.1515\/9780773591134-017"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB32","unstructured":"F. Nielsen, On the geometric piercing problem, Proc. 10th Franco-Japanese Franco-Chinese Conf. Combin. and Comp. Sci., Palaiseau, France, 1997."},{"key":"10.1016\/S0304-3975(98)00336-3_BIB33","unstructured":"F. Nielsen, On Point Covers of c-Oriented polygons, Proc. 10th Canad. Conf. Comput. Geom. p. 6 and http:\/\/cgm.cs.mcgill.ca\/cccg98\/, 1998."},{"key":"10.1016\/S0304-3975(98)00336-3_BIB34","doi-asserted-by":"crossref","first-page":"1034","DOI":"10.1137\/0220065","article-title":"New upper bounds in Klee's measure problem","volume":"20","author":"Overmars","year":"1991","journal-title":"SIAM J. Comput."},{"year":"1985","series-title":"Computational Geometry: An Introduction","author":"Preparata","key":"10.1016\/S0304-3975(98)00336-3_BIB35"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB36","doi-asserted-by":"crossref","unstructured":"D.J. Rosenkrantz, R.E. Stearns, P.M. Lewis, Approximate algorithms for the traveling salesperson problem, Proc. 15th Annu. IEEE Symp. Switching Automata Theory, 1974, pp. 33\u201342.","DOI":"10.1109\/SWAT.1974.4"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB37","doi-asserted-by":"crossref","unstructured":"P. Slav\u0131\u0301k, A tight analysis of the greedy algorithm for set cover, Proc. 28th Annual ACM Symp. on the Theory of Computing, Philadelphia, Pennsylvania, May 1996, pp. 435\u2013441.","DOI":"10.1145\/237814.237991"},{"key":"10.1016\/S0304-3975(98)00336-3_BIB38","unstructured":"G. Wegner, Eigenschaften der Nerven homologish-einfacher Familien im Rn, Ph.D. Thesis, G\u00f6ttingen, 1967."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397598003363?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397598003363?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T01:51:59Z","timestamp":1733277119000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397598003363"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,9]]},"references-count":38,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2000,9]]}},"alternative-id":["S0304397598003363"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(98)00336-3","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[2000,9]]}}}