{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:28:31Z","timestamp":1761611311143,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"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_20","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"217-228","source":"Crossref","is-referenced-by-count":14,"title":["Two Dimensional Range Minimum Queries and Fibonacci Lattices"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[]},{"given":"Pooya","family":"Davoodi","sequence":"additional","affiliation":[]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[]},{"given":"Satti","family":"Srinivasa Rao","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_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":"20_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":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-03367-4_9","volume-title":"Algorithms and Data Structures","author":"P. Bose","year":"2009","unstructured":"Bose, P., He, M., Maheshwari, A., Morin, P.: Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol.\u00a05664, pp. 98\u2013109. Springer, Heidelberg (2009)"},{"issue":"4","key":"20_CR4","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":"20_CR5","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":"1","key":"20_CR6","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/4904.4800","volume":"33","author":"B. Chor","year":"1986","unstructured":"Chor, B., Leiserson, C.E., Rivest, R.L., Shearer, J.B.: An application of number theory to the organization of raster-graphics memory. Journal of ACM\u00a033(1), 86\u2013104 (1986)","journal-title":"Journal of ACM"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Davoodi, P., Raman, R., Rao, S.S.: Succinct representations of binary trees for range minimum queries. In: Proc. 18th Annual International Conference on Computing and Combinatorics (to appear, 2012)","DOI":"10.1007\/978-3-642-32241-9_34"},{"key":"20_CR8","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. LNCS, vol.\u00a05555, pp. 341\u2013353. Springer, Heidelberg (2009)"},{"key":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/978-3-642-31594-7_28","volume-title":"ICALP 2012","author":"A. Farzan","year":"2012","unstructured":"Farzan, A., Munro, J.I., Raman, R.: Succinct Indices for Range Queries with Applications to Orthogonal Range Maxima. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol.\u00a07391, pp. 327\u2013338. Springer, Heidelberg (2012)"},{"issue":"1","key":"20_CR10","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0022-0000(86)90042-5","volume":"33","author":"A. Fiat","year":"1986","unstructured":"Fiat, A., Shamir, A.: Polymorphic arrays: A novel VLSI layout for systolic computers. Journal of Computer and System Sciences\u00a033(1), 47\u201365 (1986)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1002\/net.3230190306","volume":"19","author":"A. Fiat","year":"1989","unstructured":"Fiat, A., Shamir, A.: How to find a battleship. Networks\u00a019, 361\u2013371 (1989)","journal-title":"Networks"},{"issue":"2","key":"20_CR12","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."},{"key":"20_CR13","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":"20_CR14","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.J. Golin","year":"2011","unstructured":"Golin, M.J., 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":"20_CR15","doi-asserted-by":"crossref","unstructured":"Matousek, J.: Geometric Discrepancy. Algorithms and Combinatorics. Springer (1999)","DOI":"10.1007\/978-3-642-03942-3"},{"issue":"1","key":"20_CR16","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.jda.2006.03.011","volume":"5","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Succinct data structures for flexible text retrieval systems. Journal of Discrete Algorithms\u00a05(1), 12\u201322 (2007)","journal-title":"Journal of Discrete Algorithms"},{"issue":"4","key":"20_CR17","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","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T11:34:08Z","timestamp":1744025648000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}