{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T09:10:44Z","timestamp":1779268244476,"version":"3.51.4"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319084039","type":"print"},{"value":"9783319084046","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08404-6_4","type":"book-chapter","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T23:55:08Z","timestamp":1403654108000},"page":"38-49","source":"Crossref","is-referenced-by-count":3,"title":["Amortized Analysis of Smooth Quadtrees in All Dimensions"],"prefix":"10.1007","author":[{"given":"Huck","family":"Bennett","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chee","family":"Yap","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"4_CR1","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.comgeo.2005.09.002","volume":"34","author":"B. Aronov","year":"2006","unstructured":"Aronov, B., Bronnimann, H., Chang, A.Y., Chiang, Y.-J.: Cost prediction for ray shooting in octrees. Computational Geometry: Theory and Applications\u00a034(3), 159\u2013181 (2006)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"3","key":"4_CR2","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/S0022-0000(05)80059-5","volume":"48","author":"M.W. Bern","year":"1994","unstructured":"Bern, M.W., Eppstein, D., Gilbert, J.R.: Provably good mesh generation. J. Comput. Syst. Sci.\u00a048(3), 384\u2013409 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Bennett, H., Yap, C.: Amortized Analysis of Smooth Quadtrees in All Dimensions, \n                  \n                    http:\/\/www.cs.nyu.edu\/exact\/doc\/smoothSubdiv2014.pdf","DOI":"10.1007\/978-3-319-08404-6_4"},{"key":"4_CR4","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press (2009)"},{"key":"4_CR5","unstructured":"Core Library homepage. Software download, source, documentation and links: \n                  \n                    http:\/\/cs.nyu.edu\/exact\/core\/"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applic., 3rd edn. Springer (2008)","DOI":"10.1007\/978-3-540-77974-2"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"de Berg, M., Roeloffzen, M., Speckmann, B.: Kinetic compressed quadtrees in the black-box model with applications to collision detection for low-density scenes. In: [EF 2012], pp. 383\u2013394","DOI":"10.1007\/978-3-642-33090-2_34"},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms \u2013 ESA 2012","year":"2012","unstructured":"Epstein, L., Ferragina, P. (eds.): ESA 2012. LNCS, vol.\u00a07501. Springer, Heidelberg (2012)"},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"R.A. Finkel","year":"1974","unstructured":"Finkel, R.A., Bentley, J.L.: Quad trees: A data structure for retrieval on composite keys. Acta Inf.\u00a04, 1\u20139 (1974)","journal-title":"Acta Inf."},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-642-40104-6_43","volume-title":"Algorithms and Data Structures","author":"M. L\u00f6ffler","year":"2013","unstructured":"L\u00f6ffler, M., Simons, J.A., Strash, D.: Dynamic planar point location with sub-logarithmic local updates. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol.\u00a08037, pp. 499\u2013511. Springer, Heidelberg (2013)"},{"key":"4_CR11","unstructured":"Moore, D.: Simplicial Mesh Generation with Applications. PhD thesis, Cornell University (1992)"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Moore, D.: The cost of balancing generalized quadtrees. In: Symposium on Solid Modeling and Applications, pp. 305\u2013312 (1995)","DOI":"10.1145\/218013.218078"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BF00264354","volume":"17","author":"M.H. Overmars","year":"1982","unstructured":"Overmars, M.H., van Leeuwen, J.: Dynamic multi-dimensional data structures based on quad- and k-d trees. Acta Inf.\u00a017, 267\u2013285 (1982)","journal-title":"Acta Inf."},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Park, E., Mount, D.M.: A self-adjusting data structure for multidimensional point sets. In: [EF 2012], pp. 778\u2013789","DOI":"10.1007\/978-3-642-33090-2_67"},{"key":"4_CR15","unstructured":"Ruppert, J.: A new and simple algorithm for quality 2-dimensional mesh generation. In: SODA, pp. 83\u201392. ACM\/SIAM (1993)"},{"key":"4_CR16","unstructured":"Samet, H.: Applications of spatial data structures - computer graphics, image processing, and GIS. Addison-Wesley (1990)"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Samet, H.: The Design and Analysis of Spatial Data Structures. Addison-Wesley (1990)","DOI":"10.1007\/3-540-52208-5_28"},{"key":"4_CR18","unstructured":"Sheehy, D.R.: Private correspondence"},{"issue":"5","key":"4_CR19","doi-asserted-by":"publisher","first-page":"1627","DOI":"10.1111\/j.1467-8659.2012.03168.x","volume":"31","author":"D.R. Sheehy","year":"2012","unstructured":"Sheehy, D.R.: New Bounds on the Size of Optimal Meshes. Computer Graphics Forum\u00a031(5), 1627\u20131635 (2012)","journal-title":"Computer Graphics Forum"},{"key":"4_CR20","unstructured":"Simons, J.A.: Private correspondence"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"Wang, C., Chiang, Y.-J., Yap, C.: On soft predicates in subdivision motion planning. In: 29th SoCG, pp. 349\u2013358. ACM (2013)","DOI":"10.1145\/2462356.2462386"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08404-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T23:43:43Z","timestamp":1558914223000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08404-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319084039","9783319084046"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08404-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}