{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:23:20Z","timestamp":1725665000459},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540631651"},{"type":"electronic","value":"9783540691945"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63165-8_215","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:11:45Z","timestamp":1330297905000},"page":"605-615","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Efficient splitting and merging algorithms for order decomposable problems"],"prefix":"10.1007","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"57_CR1","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/BF02187749","volume":"4","author":"A. Aggarwal","year":"1989","unstructured":"A. Aggarwal, L. Guibas, J. Saxe and P.W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete and Computational Geometry 4 (1989), 591\u2013604.","journal-title":"Discrete and Computational Geometry"},{"key":"57_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974."},{"unstructured":"L. Arge and J.S. Vitter, Optimal dynamic interval management in external memory. 37th IEEE Symp. on Foundations of Computer Science (1996).","key":"57_CR3"},{"issue":"3","key":"57_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"R. Bayer and C. McCreight, Organization and maintenance of large ordered indexes. Acta Informatica 1, 3 (1972), 173\u2013189.","journal-title":"Acta Informatica"},{"key":"57_CR5","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"19","author":"J.L. Bentley","year":"1975","unstructured":"J.L. Bentley, Multidimensional binary search trees used for associated searching. Comm. ACM, 19 (1975), 509\u2013517.","journal-title":"Comm. ACM"},{"key":"57_CR6","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"J.L. Bentley","year":"1979","unstructured":"J.L. Bentley, Decomposable Searching Problems. Information Processing Letters, 8 (1979), 244\u2013251.","journal-title":"Information Processing Letters"},{"key":"57_CR7","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"J.L. Bentley","year":"1980","unstructured":"J.L. Bentley and J.B. Saxe, Decomposable Searching Problems I. Static-to-Dynamic Transformation. J. of Algorithms, 1 (1980), 301\u2013358.","journal-title":"J. of Algorithms"},{"unstructured":"Y.-J. Chiang and R. Tamassia, Dynamic Algorithms in Computational Geometry, Proceedings of the IEEE, Special issue on Computational Geometry, G. Toussaint, ed., 80 (1992) 1412\u20131434.","key":"57_CR8"},{"key":"57_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"R.A. Finkel","year":"1974","unstructured":"R.A. Finkel and J.L. Bentley, Quad-trees: a data structure for retrieval of composite keys. Acta Inform., 4 (1974), 1\u20139.","journal-title":"Acta Inform."},{"unstructured":"I.G. Gowda and D.G. Kirkpatrick, Exploiting linear merging and extra storage in the maintenance of fully dynamic geometric data structures. In Proc. 19th Allerton Conference on Communication, Control and Computing (1980), 1\u201310.","key":"57_CR10"},{"key":"57_CR11","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1007\/BF01759075","volume":"6","author":"M.J. Kreveld van","year":"1991","unstructured":"M.J. van Kreveld and M.H. Overmars, Divided k-d trees, Algorithmica, 6 (1991), 840\u2013858.","journal-title":"Algorithmica"},{"key":"57_CR12","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1145\/174130.174140","volume":"40","author":"M.J. Kreveld van","year":"1993","unstructured":"M.J. van Kreveld and M.H. Overmars, Union-copy structures and dynamic segment trees, J. ACM, 40 (1993), 635\u2013652.","journal-title":"J. ACM"},{"key":"57_CR13","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1006\/inco.1994.1027","volume":"110","author":"M.J. Kreveld van","year":"1994","unstructured":"M.J. van Kreveld and M.H. Overmars, Concatenable structures for decomposable problems, Information and Computation, 110 (1994), 130\u2013148.","journal-title":"Information and Computation"},{"key":"57_CR14","first-page":"121","volume":"118","author":"J. Leeuwen van","year":"1981","unstructured":"J. van Leeuwen and M.H. Overmars, The art of dynamizing. In Proc. 10th Mathematical Foundations of Computer Science, LNCS, 118 (1981), 121\u2013131.","journal-title":"Proc. 10th Mathematical Foundations of Computer Science, LNCS"},{"key":"57_CR15","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0020-0190(80)90073-3","volume":"10","author":"J. Leeuwen van","year":"1980","unstructured":"J. van Leeuwen and D. Wood, Dynamization of decomposable searching problems. Information Processing Letters, 10 (1980), 51\u201356.","journal-title":"Information Processing Letters"},{"key":"57_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01786969","volume":"15","author":"K. Mehlhorn","year":"1981","unstructured":"K. Mehlhorn, Lowerbounds on the efficiency of transforming static data structures into dynamic structures. Mathematical System Theory, 15 (1981), 1\u201316.","journal-title":"Mathematical System Theory"},{"unstructured":"K. Mehlhorn, Multi-Dimensional Searching and Computational Geometry EATCS Monographs on Theoretical Computer Science, vol. 3, Springer-Verlag, 1984.","key":"57_CR17"},{"key":"57_CR18","first-page":"17","volume-title":"Discrete Structures and Algorithms","author":"H.A. Maurer","year":"1979","unstructured":"H.A. Maurer and T.A. Ottmann, Dynamic solutions of decomposable searching problems. In Discrete Structures and Algorithms, U. Pape ed., Hanser Verlag, Wien, (1979), 17\u201324."},{"key":"57_CR19","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0020-0190(81)90010-7","volume":"12","author":"K. Mehlhorn","year":"1981","unstructured":"K. Mehlhorn and M.H. Overmars, Optimal dynamization of decomposable searching problems. Information Processing Letters, 12 (1981), 93\u201398","journal-title":"Information Processing Letters"},{"key":"57_CR20","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0196-6774(81)90025-0","volume":"2","author":"M. H. Overmars","year":"1981","unstructured":"M. H. Overmars, Dynamization of order decomposable set problems. J. Algorithms, 2 (1981), 245\u2013260.","journal-title":"J. Algorithms"},{"key":"57_CR21","volume-title":"LNCS 156","author":"M.H. Overmars","year":"1983","unstructured":"M.H. Overmars, The Design of Dynamic Data Structures, LNCS 156, Springer-Verlag, Berlin\/New York, 1983."},{"key":"57_CR22","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M.H. Overmars","year":"1981","unstructured":"M.H. Overmars and J. van Leeuwen, Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23 (1981), 166\u2013204.","journal-title":"Journal of Computer and System Sciences"},{"key":"57_CR23","first-page":"224","volume":"104","author":"M.H. Overmars","year":"1981","unstructured":"M.H. Overmars and J. van Leeuwen, Dynamization of decomposable searching problems yielding good worst-case bounds. In Proc. 5th GI Conference on Theoretical Computer Science, LNCS, 104 (1981), 224\u2013233.","journal-title":"Proc. 5th GI Conference on Theoretical Computer Science, LNCS"},{"key":"57_CR24","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0020-0190(81)90077-6","volume":"12","author":"M.H. Overmars","year":"1981","unstructured":"M.H. Overmars and J. van Leeuwen, Some principles for dynamizing decomposable searching problems. Information Processing Letters, 12 (1981), 49\u201353.","journal-title":"Information Processing Letters"},{"key":"57_CR25","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0020-0190(81)90093-4","volume":"12","author":"M.H. Overmars","year":"1981","unstructured":"M.H. Overmars and J. van Leeuwen, Worst-case optimal insertion and deletion methods for decomposable searching problems. Information Processing Letters, 12 (1981), 168\u2013173.","journal-title":"Information Processing Letters"},{"key":"57_CR26","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BF00264354","volume":"17","author":"M.H. Overmars","year":"1982","unstructured":"M.H. Overmars and J. van Leeuwen, Dynamic Multi-dimensional data structures based on quad-and k-d trees. Acta Inform., 17 (1982), 267\u2013285.","journal-title":"Acta Inform."},{"key":"57_CR27","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/978-3-642-71071-1_11","volume-title":"Data Structures for Raster Graphics","author":"H. Samet","year":"1986","unstructured":"H. Samet, Bibliography on quad-trees and related hierarchical data structures. In Data Structures for Raster Graphics, L. Kessenaar, F. Peters, and M. van Lierop eds., Springer-Verlag, Berlin, (1986), 181\u2013201."},{"key":"57_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0747-7171(89)80002-1","volume":"7","author":"H.W. Scholten","year":"1989","unstructured":"H.W. Scholten and M.H. Overmars, General methods for adding range restrictions to decomposable searching problems, J. of Symbolic Computation, 7 (1989), 1\u201310.","journal-title":"J. of Symbolic Computation"},{"key":"57_CR29","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1145\/3828.3839","volume":"32","author":"D.E. Willard","year":"1985","unstructured":"D.E. Willard and G.S. Lueker, Adding range restriction capability to dynamic data structures, J. ACM, 32 (1985), 597\u2013617.","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63165-8_215","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T02:15:26Z","timestamp":1578536126000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63165-8_215"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540631651","9783540691945"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-63165-8_215","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"8 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}