{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T15:24:49Z","timestamp":1760369089348},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_67","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"778-789","source":"Crossref","is-referenced-by-count":3,"title":["A Self-adjusting Data Structure for Multidimensional Point Sets"],"prefix":"10.1007","author":[{"given":"Eunhui","family":"Park","sequence":"first","affiliation":[]},{"given":"David M.","family":"Mount","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"67_CR1","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/1240233.1240240","volume":"3","author":"S. Arya","year":"2007","unstructured":"Arya, S., Malamatos, T., Mount, D.M.: A simple entropy-based algorithm for planar point location. ACM Trans. Algorithms, 3, article: 17 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"67_CR2","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1137\/S0097539704446724","volume":"37","author":"S. Arya","year":"2007","unstructured":"Arya, S., Malamatos, T., Mount, D.M., Wong, K.-C.: Optimal expected-case planar point location. SIAM J. Comput.\u00a037, 584\u2013610 (2007)","journal-title":"SIAM J. Comput."},{"key":"67_CR3","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0925-7721(00)00022-5","volume":"17","author":"S. Arya","year":"2001","unstructured":"Arya, S., Mount, D.M.: Approximate range searching. Comput. Geom. Theory Appl.\u00a017, 135\u2013163 (2001)","journal-title":"Comput. Geom. Theory Appl."},{"key":"67_CR4","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S. Arya","year":"1998","unstructured":"Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.: An optimal algorithm for approximate nearest neighbor searching. J. Assoc. Comput. Mach.\u00a045, 891\u2013923 (1998)","journal-title":"J. Assoc. Comput. Mach."},{"key":"67_CR5","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0190(93)90222-U","volume":"45","author":"M. Bern","year":"1993","unstructured":"Bern, M.: Approximate closest-point queries in high dimensions. Inform. Process. Lett.\u00a045, 95\u201399 (1993)","journal-title":"Inform. Process. Lett."},{"key":"67_CR6","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2007.03.002","volume":"382","author":"M. B\u0103doiu","year":"2007","unstructured":"B\u0103doiu, M., Cole, R., Demaine, E.D., Iacono, J.: A unified access bound on comparison-based dynamic dictionaries. Theo. Comp. Sci.\u00a0382, 86\u201396 (2007)","journal-title":"Theo. Comp. Sci."},{"key":"67_CR7","unstructured":"Chan, T.: A minimalist\u2019s implementation of an approximate nearest neighbor algorithm in fixed dimensions (2006), http:\/\/www.cs.uwaterloo.ca\/~tmchan\/pub.html (unpublished manuscript)"},{"key":"67_CR8","unstructured":"Chan, T.M.: Closest-point problems simplified on the ram. In: Proc. 13th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp. 472\u2013473 (2002)"},{"key":"67_CR9","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Fast algorithms for the all nearest neighbors problem. In: Proc. 24th Annu. IEEE Sympos. Found. Comput. Sci., pp. 226\u2013232 (1983)","DOI":"10.1109\/SFCS.1983.16"},{"key":"67_CR10","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1137\/S009753979732699X","volume":"30","author":"R. Cole","year":"2000","unstructured":"Cole, R.: On the dynamic finger conjecture for splay trees. Part 2 The proof. SIAM J. Comput.\u00a030, 44\u201385 (2000)","journal-title":"SIAM J. Comput."},{"key":"67_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539797326988","volume":"30","author":"R. Cole","year":"2000","unstructured":"Cole, R., Mishra, B., Schmidt, J., Siegel, A.: On the dynamic finger conjecture for splay trees. Part 1: Splay sorting log n-block sequences. SIAM J. Comput.\u00a030, 1\u201343 (2000)","journal-title":"SIAM J. Comput."},{"key":"67_CR12","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Harmon, D., Iacono, J., P\u01cetra\u015fcu, M.: The geometry of binary search tree. In: Proc. 20th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp. 496\u2013505 (2009)","DOI":"10.1137\/1.9781611973068.55"},{"key":"67_CR13","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1016\/j.tcs.2004.01.019","volume":"314","author":"A. Elmasry","year":"2004","unstructured":"Elmasry, A.: On the sequential access theorem and deque conjecture for splay trees. Theo. Comp. Sci.\u00a0314, 459\u2013466 (2004)","journal-title":"Theo. Comp. Sci."},{"key":"67_CR14","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1142\/S0218195908002568","volume":"18","author":"D. Eppstein","year":"2008","unstructured":"Eppstein, D., Goodrich, M.T., Sun, J.Z.: The skip quadtree: A simple dynamic data structure for multidimensional data. Internat. J. Comput. Geom. Appl.\u00a018, 131\u2013160 (2008)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"67_CR15","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.ipl.2007.10.001","volume":"106","author":"G.F. Georgakopoulos","year":"2008","unstructured":"Georgakopoulos, G.F.: Chain-splay trees, or, how to achieve and prove loglogN-competitiveness by splaying. Inform. Process. Lett.\u00a0106, 37\u201343 (2008)","journal-title":"Inform. Process. Lett."},{"key":"67_CR16","volume-title":"Geometric Approximation Algorithms","author":"S. Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. American Mathematical Society, Providence (2011)"},{"key":"67_CR17","unstructured":"Iacono, J.: Alternatives to splay trees with O(logn) worst-case access times. In: Proc. 12th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp. 516\u2013522 (2001)"},{"key":"67_CR18","unstructured":"Iacono, J.: Distribution-sensitive data structures. PhD thesis, Rutgers, The state University of New Jersey, New Brunswick, New Jersey (2001)"},{"key":"67_CR19","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.comgeo.2004.03.010","volume":"29","author":"J. Iacono","year":"2004","unstructured":"Iacono, J.: Expected asymptotically optimal planar point location. Comput. Geom. Theory Appl.\u00a029, 19\u201322 (2004)","journal-title":"Comput. Geom. Theory Appl."},{"key":"67_CR20","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-004-1136-8","volume":"42","author":"J. Iacono","year":"2005","unstructured":"Iacono, J.: Key-independent optimality. Algorithmica\u00a042, 3\u201310 (2005)","journal-title":"Algorithmica"},{"key":"67_CR21","doi-asserted-by":"crossref","unstructured":"Mount, D.M., Park, E.: A dynamic data structure for approximate range searching. In: Proc. 26th Annu. Sympos. Comput. Geom., pp. 247\u2013256 (2010)","DOI":"10.1145\/1810959.1811002"},{"key":"67_CR22","unstructured":"Pettie, S.: Splay trees, Davenport-Schinzel sequences, and the deque conjecture. In: Proc. 19th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp. 1115\u20131124 (2008)"},{"key":"67_CR23","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W. Pugh","year":"1990","unstructured":"Pugh, W.: Skip lists: A probabilistic alternative to balanced trees. Commun. ACM\u00a033, 668\u2013676 (1990)","journal-title":"Commun. ACM"},{"key":"67_CR24","volume-title":"Foundations of Multidimensional and Metric Data Structures","author":"H. Samet","year":"2006","unstructured":"Samet, H.: Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann, San Francisco (2006)"},{"key":"67_CR25","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/BF01940876","volume":"16","author":"R. Seidel","year":"1996","unstructured":"Seidel, R., Aragon, C.: Randomized search trees. Algorithmica\u00a016, 464\u2013497 (1996)","journal-title":"Algorithmica"},{"key":"67_CR26","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. Assoc. Comput. Mach.\u00a032, 652\u2013686 (1985)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"67_CR27","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jagm.1996.0025","volume":"20","author":"A. Subramanian","year":"1996","unstructured":"Subramanian, A.: An explanation of splaying. J. Algorithms\u00a020(3), 512\u2013525 (1996)","journal-title":"J. Algorithms"},{"key":"67_CR28","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF01191208","volume":"12","author":"R. Sundar","year":"1992","unstructured":"Sundar, R.: On the deque conjecture for the splay algorithm. Combinatorica\u00a012, 95\u2013124 (1992)","journal-title":"Combinatorica"},{"key":"67_CR29","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/BF02579253","volume":"5","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Sequential access in splay trees takes linear time. Combinatorica\u00a05, 367\u2013378 (1985)","journal-title":"Combinatorica"},{"key":"67_CR30","doi-asserted-by":"crossref","unstructured":"Wang, C.C., Derryberry, J., Sleator, D.D.: o(loglogn)-competitive dynamic binary search trees. In: Proc. 17th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp. 374\u2013383 (2006)","DOI":"10.1145\/1109557.1109600"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_67.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,25]],"date-time":"2023-06-25T13:10:23Z","timestamp":1687698623000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_67"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_67","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}