{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T15:10:05Z","timestamp":1745939405503,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642359255"},{"type":"electronic","value":"9783642359262"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-35926-2_30","type":"book-chapter","created":{"date-parts":[[2012,12,21]],"date-time":"2012-12-21T04:32:11Z","timestamp":1356064331000},"page":"280-287","source":"Crossref","is-referenced-by-count":1,"title":["Range Extremum Queries"],"prefix":"10.1007","author":[{"given":"Rajeev","family":"Raman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/978-3-540-73437-6_29","volume-title":"Combinatorial Pattern Matching","author":"A. Amir","year":"2007","unstructured":"Amir, A., Fischer, J., Lewenstein, M.: Two-Dimensional Range Minimum Queries. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 286\u2013294. Springer, Heidelberg (2007)"},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"Atallah, M.J., Yuan, H.: Data structures for range minimum queries in multidimensional arrays. In: Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 150\u2013160. SIAM (2010)","DOI":"10.1137\/1.9781611973075.14"},{"key":"30_CR3","unstructured":"Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. In: Bansal, N., Pruhs, K., Stein, C. (eds.) SODA, pp. 680\u2013689. SIAM (2007)"},{"key":"30_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/3-540-45465-9_18","volume-title":"Automata, Languages and Programming","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Cole, R., Raman, R.: Exponential Structures for Efficient Cache-Oblivious Algorithms. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 195\u2013207. Springer, Heidelberg (2002)"},{"issue":"5","key":"30_CR5","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"J.L. Bentley","year":"1979","unstructured":"Bentley, J.L.: Decomposable searching problems. Information Processing Letters\u00a08(5), 244\u2013251 (1979)","journal-title":"Information Processing Letters"},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"Bose, P., Chen, E.Y., He, M., Maheshwari, A., Morin, P.: Succinct geometric indexes supporting point location queries. In: Mathieu, C. (ed.) SODA, pp. 635\u2013644. SIAM (2009)","DOI":"10.1137\/1.9781611973068.70"},{"key":"30_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-642-33090-2_20","volume-title":"Algorithms \u2013 ESA 2012","author":"G.S. Brodal","year":"2012","unstructured":"Brodal, G.S., Davoodi, P., Lewenstein, M., Raman, R., Rao, S.S.: Two Dimensional Range Minimum Queries and Fibonacci Lattices. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol.\u00a07501, pp. 217\u2013228. Springer, Heidelberg (2012)"},{"issue":"4","key":"30_CR8","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1007\/s00453-011-9499-0","volume":"63","author":"G.S. Brodal","year":"2012","unstructured":"Brodal, G.S., Davoodi, P., Rao, S.S.: On space efficient two dimensional range minimum data structures. Algorithmica\u00a063(4), 815\u2013830 (2012)","journal-title":"Algorithmica"},{"key":"30_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1007\/978-3-642-10631-6_83","volume-title":"Algorithms and Computation","author":"G.S. Brodal","year":"2009","unstructured":"Brodal, G.S., J\u00f8rgensen, A.G.: Data Structures for Range Median Queries. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 822\u2013831. Springer, Heidelberg (2009)"},{"key":"30_CR10","first-page":"1","volume-title":"Proceedings of the 27th Annual ACM Symposium on Computational Geometry, SoCG 2011","author":"T.M. Chan","year":"2011","unstructured":"Chan, T.M., Larsen, K.G., P\u0103tra\u015fcu, M.: Orthogonal range searching on the ram, revisited. In: Proceedings of the 27th Annual ACM Symposium on Computational Geometry, SoCG 2011, pp. 1\u201310. ACM, New York (2011), http:\/\/doi.acm.org\/10.1145\/1998196.1998198"},{"issue":"2","key":"30_CR11","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/07068669X","volume":"39","author":"T.M. Chan","year":"2009","unstructured":"Chan, T.M., Patrascu, M.: Transdichotomous results in computational geometry, I: Point location in sublogarithmic time. SIAM J. Comput.\u00a039(2), 703\u2013729 (2009)","journal-title":"SIAM J. Comput."},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Rosenberg, B.: Computing partial sums in multidimensional arrays. In: Proc. 5th Annual Symposium on Computational Geometry, pp. 131\u2013139. ACM (1989)","DOI":"10.1145\/73833.73848"},{"issue":"3","key":"30_CR13","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B. Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput.\u00a017(3), 427\u2013462 (1988); prel. vers. FOCS 1985","journal-title":"SIAM J. Comput."},{"key":"30_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/978-3-642-32241-9_34","volume-title":"Computing and Combinatorics","author":"P. Davoodi","year":"2012","unstructured":"Davoodi, P., Raman, R., Rao, S.S.: Succinct Representations of Binary Trees for Range Minimum Queries. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol.\u00a07434, pp. 396\u2013407. Springer, Heidelberg (2012)"},{"key":"30_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-642-02927-1_29","volume-title":"Automata, Languages and Programming","author":"E.D. Demaine","year":"2009","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On Cartesian Trees and Range Minimum Queries. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 341\u2013353. Springer, Heidelberg (2009)"},{"issue":"2","key":"30_CR16","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J. Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput.\u00a040(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"30_CR17","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1145\/1198513.1198521","volume":"2","author":"L. Foschini","year":"2006","unstructured":"Foschini, L., Grossi, R., Gupta, A., Vitter, J.S.: When indexing equals compression: Experiments with compressing suffix arrays and applications. ACM Trans. Algorithms\u00a02(4), 611\u2013639 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"30_CR18","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. 16th Annual ACM Symposium on Theory of Computing, pp. 135\u2013143. ACM (1984)","DOI":"10.1145\/800057.808675"},{"key":"30_CR19","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. 16th Annual ACM Symposium on Theory of Computing, pp. 135\u2013143. ACM (1984)","DOI":"10.1145\/800057.808675"},{"key":"30_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-25591-5_20","volume-title":"Algorithms and Computation","author":"M. Golin","year":"2011","unstructured":"Golin, M., Iacono, J., Krizanc, D., Raman, R., Rao, S.S.: Encoding 2D Range Maximum Queries. In: Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 180\u2013189. Springer, Heidelberg (2011)"},{"key":"30_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1007\/978-3-540-30551-4_49","volume-title":"Algorithms and Computation","author":"J. J\u00e1J\u00e1","year":"2004","unstructured":"J\u00e1J\u00e1, J., Mortensen, C.W., Shi, Q.: Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 558\u2013568. Springer, Heidelberg (2004)"},{"issue":"1","key":"30_CR22","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00454-010-9308-6","volume":"45","author":"H. Kaplan","year":"2011","unstructured":"Kaplan, H., Ramos, E., Sharir, M.: Range minima queries with respect to a random permutation, and approximate range counting. Discrete & Computational Geometry\u00a045(1), 3\u201333 (2011)","journal-title":"Discrete & Computational Geometry"},{"key":"30_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/978-3-642-02882-3_22","volume-title":"Computing and Combinatorics","author":"M. Karpinski","year":"2009","unstructured":"Karpinski, M., Nekrich, Y.: Space Efficient Multi-dimensional Range Reporting. In: Ngo, H.Q. (ed.) COCOON 2009. LNCS, vol.\u00a05609, pp. 215\u2013224. Springer, Heidelberg (2009)"},{"key":"30_CR24","unstructured":"Mehta, D.P., Sahni, S. (eds.): Handbook of Data Structures and Applications. Chapman & Hall\/CRC (2009)"},{"issue":"4","key":"30_CR25","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.comgeo.2008.09.001","volume":"42","author":"Y. Nekrich","year":"2009","unstructured":"Nekrich, Y.: Orthogonal range searching in linear and almost-linear space. Comput. Geom.\u00a042(4), 342\u2013351 (2009)","journal-title":"Comput. Geom."},{"key":"30_CR26","doi-asserted-by":"crossref","unstructured":"Patrascu, M. (data) structures. In: FOCS, pp. 434\u2013443. IEEE Computer Society Press (2008)","DOI":"10.1109\/FOCS.2008.69"},{"key":"30_CR27","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Kleinberg, J.M. (ed.) STOC, pp. 232\u2013240. ACM (2006)","DOI":"10.1145\/1132516.1132551"},{"issue":"4","key":"30_CR28","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J. Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Communications of the ACM\u00a023(4), 229\u2013239 (1980)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-35926-2_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T14:43:32Z","timestamp":1745937812000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-35926-2_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642359255","9783642359262"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-35926-2_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}