{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T09:48:53Z","timestamp":1747907333227},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633075"},{"type":"electronic","value":"9783540694229"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63307-3_69","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T19:22:48Z","timestamp":1270495368000},"page":"297-306","source":"Crossref","is-referenced-by-count":7,"title":["Dynamic data structures for fat objects and their applications"],"prefix":"10.1007","author":[{"given":"Alon","family":"Efrat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Franck","family":"Nielsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1137\/0221035","volume":"21","author":"P. K. Agarwal","year":"1992","unstructured":"P. K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number, SIAM J. Comput. 21 (1992), 540\u2013570","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"P.K. Agarwal, A. Efrat and M. Sharir, Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications, Proc. 11th ACM Symp. Comput. Geom., 1995, 39\u201350.","key":"27_CR2","DOI":"10.1145\/220279.220284"},{"key":"27_CR3","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0925-7721(95)00005-8","volume":"5","author":"P.K. Agarwal","year":"1995","unstructured":"P.K. Agarwal, M.J. Katz and M. Sharir, Computing depth orders and related problems, Computational Geometry: Theory and Applications 5 (1995), 187\u2013206.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"27_CR4","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF01293483","volume":"14","author":"P.K. Agarwal","year":"1995","unstructured":"P.K. Agarwal and J. Matou\u0161ek, Dynamic half-space range reporting and its applications, Algorithmica 14 (1995), 325\u2013345.","journal-title":"Algorithmica"},{"key":"27_CR5","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/BF01758853","volume":"8","author":"H. Alt","year":"1992","unstructured":"H. Alt, R. Fleischer, M. Kaufmann, K. Mehlhorn, S. N\u00e4her, S. Schirra and C. Uhrig, Approximate motion planning and the complexity of the boundary of the union of simple geometric figures, Algorithmica 8 (1992), 391\u2013406.","journal-title":"Algorithmica"},{"key":"27_CR6","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"J. Bentley","year":"1980","unstructured":"J. Bentley and J. Saxe, Decomposable searching problems I: Static-to-dynamic transformation, J. Algorithms 1 (1980), 301\u2013358.","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"M. de Berg, M. de Groot and M. Overmars, New Results on Binary Space Partitions in the Plane, Proc. 4th Scandinavian Workshop on Algorithm Theory, 1994, 61\u201372.","key":"27_CR7","DOI":"10.1007\/3-540-58218-5_6"},{"key":"27_CR8","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02570718","volume":"14","author":"H. Br\u00f6nnimann","year":"1995","unstructured":"H. Br\u00f6nnimann and M.T. Goodrich, Almost optimal set covers in finite VCDimension, Discrete and Computational Geometry 14 (1995), 263\u2013279.","journal-title":"Discrete and Computational Geometry"},{"key":"27_CR9","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chvatal","year":"1979","unstructured":"V. Chvatal, A greedy heuristic for the set-covering problem, Math. Oper. Res., 4 (1979),233\u2013235.","journal-title":"Math. Oper. Res."},{"key":"27_CR10","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0925-7721(93)90009-U","volume":"3","author":"K. L. Clarkson","year":"1993","unstructured":"K. L. Clarkson, K. Mehlhorn, and R. Seidel, Four results on randomized incremental constructions, Computational Geometry: Theory and Applications 3 (1993), 185\u2013212.","journal-title":"Computational Geometry: Theory and Applications"},{"doi-asserted-by":"crossref","unstructured":"A. Efrat and A. Itai, Improvements on bottleneck matching and related problems, using geometry, Proc. 12th ACM Symp. Comput. Geom., 1996, 301\u2013310. See also: A. Efrat, M.J. Katz and A. Itai, Improvements on bottleneck matching and related problems, using geometry, in preparation.","key":"27_CR11","DOI":"10.1145\/237218.237399"},{"doi-asserted-by":"crossref","unstructured":"A. Efrat and M. Sharir, On the Complexity of the Union of Fat Objects in the Plane, Proceedings 13 Annual Symposium on Computational Geometry, 1997, to appear.","key":"27_CR12","DOI":"10.1145\/262839.262911"},{"issue":"3","key":"27_CR13","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R.J. Fowler","year":"1981","unstructured":"R.J. Fowler, M.S. Paterson, and S.L. Tanimoto, Optimal packing and covering in the plane are NP-complete, Information Processing Letters 12 (3) (1981), 133\u2013137.","journal-title":"Information Processing Letters"},{"key":"27_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1007\/3-540-52846-6_106","volume-title":"Proceedings 2 Scand. Workshop on Algorithms Theory","author":"J. Hershberger","year":"1990","unstructured":"J. Hershberger and S. Suri, Applications of a semi-dynamic convex hull algorithm, Proceedings 2 Scand. Workshop on Algorithms Theory, Lecture Notes in Computer Science, 1990, vol. 447, Springer-Verlag, New York-Berlin-Heidelberg, 380\u2013392."},{"unstructured":"M.J. Katz, 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects, tech. Report 2583, INRIA, BP93, 06902 Sophia-Antipolis, France, 1995.","key":"27_CR15"},{"key":"27_CR16","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0925-7721(92)90024-M","volume":"2","author":"M.J. Katz","year":"1992","unstructured":"M.J. Katz, M.H. Overmars, M. Sharir, Efficient hidden surface removal for objects with small union size, Computational Geometry: Theory and Applications 2 (1992), 223\u2013234.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"27_CR17","volume-title":"New Results on Data Structures in Computational Geometry","author":"M. J. Kreveld van","year":"1992","unstructured":"M. J. van Kreveld, New Results on Data Structures in Computational Geometry, Ph.D. Dissertation, Dept. Comput. Sci., Utrecht Univ., Utrecht, Netherlands, 1992."},{"key":"27_CR18","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J. Matousek","year":"1992","unstructured":"J. Matousek, Efficient partition trees, Discrete and Computational Geometry 8 (1992),315\u2013334.","journal-title":"Discrete and Computational Geometry"},{"key":"27_CR19","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"J. Matou\u0161ek, Range searching with efficient hierarchical cuttings, Discrete and Computational Geometry 10 (1993), 157\u2013182.","journal-title":"Discrete and Computational Geometry"},{"unstructured":"F. Nielsen and M. Yvinec, Output-Sensitive Convex Hull Algorithms of Planar Convex Objects, Research Report 2575 INRIA, BP93, 06902 Sophia-Antipolis, France.","key":"27_CR20"},{"key":"27_CR21","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0020-0190(92)90211-D","volume":"44","author":"M.H. Overmars","year":"1992","unstructured":"M.H. Overmars, Point location in fat subdivisions, Information Processing Letters 44 (1992), 261\u2013265.","journal-title":"Information Processing Letters"},{"key":"27_CR22","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"H. Overmars","year":"1981","unstructured":"H. Overmars and J. van Leeuwen, Maintenance of configurations in the plane, J. Comput. Syst. Sci. 23 (1981), 166\u2013204.","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"M.H. Overmars and A.F. van der Stappen, Range searching and point location among fat objects, Proc. 2nd Annual European Symp. on Algorithms, 1994, 240\u2013253. (See also: Tech. Report UU-CS-1994-30, Dept. of Computer Science, Utrecht University.)","key":"27_CR23","DOI":"10.1007\/BFb0049412"},{"doi-asserted-by":"crossref","unstructured":"O. Schwarzkopf and J. Vleugels, Range Searching in Low-Density Environments, Tech. Report UU-CS-1996-26, Dept. of Computer Science, Utrecht University.","key":"27_CR24","DOI":"10.1016\/S0020-0190(96)00154-8"},{"key":"27_CR25","volume-title":"Davenport Schinzel Sequences and Their Geometric Applications","author":"M. Sharir","year":"1995","unstructured":"M. Sharir and P.K. Agarwal, Davenport Schinzel Sequences and Their Geometric Applications, Cambridge University Press, New York, 1995."},{"doi-asserted-by":"crossref","unstructured":"A.F. van der Stappen, Motion Planning amidst Fat Obstacles, Ph.D. thesis, Utrecht University, 1994.","key":"27_CR26","DOI":"10.1145\/177424.177453"},{"key":"27_CR27","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/0925-7721(93)90007-S","volume":"3","author":"A.F. Stappen van der","year":"1993","unstructured":"A.F. van der Stappen, D. Halperin and M.H. Overmars, The complexity of the free space for a robot moving amidst fat obstacles, Computational Geometry: Theory and Applications 3 (1993), 353\u2013373.","journal-title":"Computational Geometry: Theory and Applications"},{"doi-asserted-by":"crossref","unstructured":"A.F. van der Stappen and M.H. Overmars, Motion planning amidst fat obstacles, Proc. 1Oth ACM Symp. Comput. Geom., 1994, 31\u201340.","key":"27_CR28","DOI":"10.1145\/177424.177453"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63307-3_69","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T18:24:11Z","timestamp":1685557451000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63307-3_69"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633075","9783540694229"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-63307-3_69","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}