{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T05:23:47Z","timestamp":1740374627645,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2010,8,7]],"date-time":"2010-08-07T00:00:00Z","timestamp":1281139200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,2]]},"DOI":"10.1007\/s00453-010-9440-y","type":"journal-article","created":{"date-parts":[[2010,8,6]],"date-time":"2010-08-06T14:31:22Z","timestamp":1281105082000},"page":"21-37","source":"Crossref","is-referenced-by-count":1,"title":["Biased Range Trees"],"prefix":"10.1007","volume":"62","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Howat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,8,7]]},"reference":[{"key":"9440_CR1","doi-asserted-by":"crossref","unstructured":"Afshani, P., Barbay, J., Chan, T.M.: Instance-optimal geometric algorithms. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp.\u00a0129\u2013138 (2009)","DOI":"10.1109\/FOCS.2009.34"},{"key":"9440_CR2","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/conm\/223\/03131","volume-title":"Advances in Discrete and Computational Geometry","author":"P.K. Agarwal","year":"1999","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Advances in Discrete and Computational Geometry. Contemporary Mathematics, vol.\u00a0223, pp.\u00a01\u201356. AMS, Providence (1999)"},{"key":"9440_CR3","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: New data structures for orthogonal range searching. In: The 41st Annual Symposium on Foundations of Computer Science, pp.\u00a0198\u2013207 (2000)","DOI":"10.1109\/SFCS.2000.892088"},{"key":"9440_CR4","doi-asserted-by":"crossref","unstructured":"Arya, S., Cheng, S.W., Mount, D.M., Ramesh, H.: Efficient expected-case algorithms for planar point location. In: Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, pp.\u00a0353\u2013366 (2000)","DOI":"10.1007\/3-540-44985-X_31"},{"key":"9440_CR5","doi-asserted-by":"crossref","unstructured":"Arya, S., Malamatos, T., Mount, D.M.: Nearly optimal expected-case planar point location. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp.\u00a0208\u2013218 (2000)","DOI":"10.1109\/SFCS.2000.892108"},{"key":"9440_CR6","unstructured":"Arya, S., Malamatos, T., Mount, D.M.: Entropy-preserving cuttings and space-efficient planar point location. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0256\u2013261 (2001)"},{"key":"9440_CR7","unstructured":"Arya, S., Malamatos, T., Mount, D.M.: A\u00a0simple entropy-based algorithm for planar point location. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0262\u2013268 (2001)"},{"issue":"2","key":"9440_CR8","doi-asserted-by":"crossref","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. 37(2), 584\u2013610 (2007)","journal-title":"SIAM J. Comput."},{"key":"9440_CR9","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"J.L. Bentley","year":"1975","unstructured":"Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18, 509\u2013517 (1975)","journal-title":"Commun. ACM"},{"key":"9440_CR10","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/358841.358850","volume":"23","author":"J.L. Bentley","year":"1980","unstructured":"Bentley, J.L.: Multidimensional divide-and-conquer. Commun. ACM 23, 214\u2013229 (1980)","journal-title":"Commun. ACM"},{"key":"9440_CR11","doi-asserted-by":"crossref","unstructured":"Chan, T.M., P\u01cetras\u00e7u, M.: Counting inversions, offline orthogonal range counting, and related problems. In: Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp.\u00a0161\u2013173 (2010)","DOI":"10.1137\/1.9781611973075.15"},{"key":"9440_CR12","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: a\u00a0new approach to query-answering. SIAM J. Comput. 15, 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"key":"9440_CR13","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B. Chazelle","year":"1988","unstructured":"Chazelle, B.: A\u00a0functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17, 427\u2013462 (1988)","journal-title":"SIAM J. Comput."},{"key":"9440_CR14","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B., Guibas, L.J.: Fractional cascading: I. A\u00a0data structuring technique. Algorithmica 1, 133\u2013162 (1986)","journal-title":"Algorithmica"},{"key":"9440_CR15","unstructured":"Collette, S., Dujmovi\u0107, V., Iacono, J., Langerman, S., Morin, P.: Distribution-sensitive point location in convex subdivisions. In: Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp.\u00a0912\u2013921 (2008)"},{"key":"9440_CR16","unstructured":"Collette, S., Dujmovi\u0107, V., Iacono, J., Langerman, S., Morin, P.: Entropy, triangulation, and point location in planar subdivisions. Technical Report. arXiv:0905.3584 [cs], March 2009"},{"key":"9440_CR17","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, third edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"9440_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03427-9","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"1997","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer, Heidelberg (1997)"},{"key":"9440_CR19","doi-asserted-by":"crossref","unstructured":"Dujmovi\u0107, V., Howat, J., Morin, P.: Biased range trees. In: Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp.\u00a0486\u2013495 (2009)","DOI":"10.1137\/1.9781611973068.54"},{"key":"9440_CR20","first-page":"696","volume":"28","author":"M.L. Fredman","year":"1981","unstructured":"Fredman, M.L.: A\u00a0lower bound on the complexity of orthogonal range queries. J.\u00a0ACM 28, 696\u2013705 (1981)","journal-title":"J.\u00a0ACM"},{"key":"9440_CR21","unstructured":"Iacono, J.: Optimal planar point location. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0240\u2013241 (2001)"},{"issue":"1","key":"9440_CR22","doi-asserted-by":"crossref","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. 29(1), 19\u201322 (2004)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9440_CR23","doi-asserted-by":"crossref","unstructured":"J\u00e1j\u00e1, J., Mortensen, C.W., Shi, Q.: Space-efficient and fast algorithms for multidimensional dominance counting and related problems. In: Proceedings of the 15th International Symposium on Algorithms and Computation, pp.\u00a0558\u2013568 (2004)","DOI":"10.1007\/978-3-540-30551-4_49"},{"key":"9440_CR24","doi-asserted-by":"crossref","unstructured":"Luecker, G.S.: A\u00a0data structure for orthogonal range queries. In: Proceedings of the 19th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp.\u00a028\u201334 (1978)","DOI":"10.1109\/SFCS.1978.1"},{"key":"9440_CR25","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/BF00264563","volume":"5","author":"K. Mehlhorn","year":"1975","unstructured":"Mehlhorn, K.: Nearly optimal binary search trees. Acta Inform. 5, 287\u2013295 (1975)","journal-title":"Acta Inform."},{"key":"9440_CR26","volume-title":"The Design and Analysis of Spatial Data Structures","author":"H. Samet","year":"1990","unstructured":"Samet, H.: The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading (1990)"},{"key":"9440_CR27","doi-asserted-by":"crossref","unstructured":"Shannon, C.E.: A\u00a0mathematical theory of communication. Bell Syst. Tech.\u00a0J. 379\u2013423 and 623\u2013656 (1948)","DOI":"10.1002\/j.1538-7305.1948.tb00917.x"},{"key":"9440_CR28","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0214022","volume":"14","author":"A.C. Yao","year":"1985","unstructured":"Yao, A.C.: On the complexity of maintaining partial sums. SIAM J. Comput. 14, 277\u2013288 (1985)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9440-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9440-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9440-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T22:25:45Z","timestamp":1740349545000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9440-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8,7]]},"references-count":28,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["9440"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9440-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2010,8,7]]}}}