{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T20:01:49Z","timestamp":1743019309732,"version":"3.40.3"},"publisher-location":"Cham","reference-count":14,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319213972"},{"type":"electronic","value":"9783319213989"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21398-9_40","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T15:12:41Z","timestamp":1435072361000},"page":"507-520","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Optimal Algorithms for Running Max and Min Filters on Random Inputs"],"prefix":"10.1007","author":[{"given":"Hongyu","family":"Liang","sequence":"first","affiliation":[]},{"given":"Shengxin","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Hao","family":"Yuan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"issue":"7","key":"40_CR1","doi-asserted-by":"publisher","first-page":"3191","DOI":"10.1109\/TSP.2008.920141","volume":"56","author":"D Coltuc","year":"2008","unstructured":"Coltuc, D.: Mathematical complexity of running filters on semi-groups and related problems. IEEE Transactions on Signal Processing 56(7), 3191\u20133197 (2008)","journal-title":"IEEE Transactions on Signal Processing"},{"key":"40_CR2","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms, 3rd edn. MIT press (2009)"},{"key":"40_CR3","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pp. 135\u2013143 (1984)","DOI":"10.1145\/800057.808675"},{"issue":"5","key":"40_CR4","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1109\/34.589214","volume":"19","author":"DZ Gevorkian","year":"1997","unstructured":"Gevorkian, D.Z., Astola, J.T., Atourian, S.M.: Improving Gil-Werman algorithm for running min and max filters. IEEE Transactions on Pattern Analysis and Machine Intelligence 19(5), 526\u2013529 (1997)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"12","key":"40_CR5","doi-asserted-by":"publisher","first-page":"1606","DOI":"10.1109\/TPAMI.2002.1114852","volume":"24","author":"J Gil","year":"2002","unstructured":"Gil, J., Kimmel, R.: Efficient dilation, erosion, opening, and closing algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence 24(12), 1606\u20131617 (2002)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"5","key":"40_CR6","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1109\/34.211471","volume":"15","author":"J Gil","year":"1993","unstructured":"Gil, J., Werman, M.: Computing 2-D min, median, and max filters. IEEE Transactions on Pattern Analysis and Machine Intelligence 15(5), 504\u2013507 (1993)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"4","key":"40_CR7","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1109\/TPAMI.1987.4767941","volume":"9","author":"RM Haralick","year":"1987","unstructured":"Haralick, R.M., Sternberg, S.R., Zhuang, X.: Image analysis using mathematical morphology. IEEE Transactions on Pattern Analysis and Machine Intelligence 9(4), 532\u2013550 (1987)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"2","key":"40_CR8","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tagjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing 13(2), 338\u2013355 (1984)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"40_CR9","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1109\/31.90400","volume":"36","author":"I Pitas","year":"1989","unstructured":"Pitas, I.: Fast algorithms for running ordering and max\/min calculation. IEEE Transactions on Circuits and Systems 36(6), 795\u2013804 (1989)","journal-title":"IEEE Transactions on Circuits and Systems"},{"key":"40_CR10","unstructured":"Soille, P.: Morphological Image Analysis: Principles and Applications. Springer-Verlag New York, Inc. (2003)"},{"issue":"7","key":"40_CR11","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1016\/0167-8655(92)90069-C","volume":"13","author":"M van Herk","year":"1992","unstructured":"van Herk, M.: A fast algorithm for local minimum and maximum filters on rectangular and octagonal kernels. Pattern Recognition Letters 13(7), 517\u2013521 (1992)","journal-title":"Pattern Recognition Letters"},{"issue":"4","key":"40_CR12","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 23(4), 229\u2013239 (1980)","journal-title":"Communications of the ACM"},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Yuan, H., Atallah, M.J.: Data structures for range minimum queries in multidimensional arrays. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 150\u2013160 (2010)","DOI":"10.1137\/1.9781611973075.14"},{"issue":"12","key":"40_CR14","doi-asserted-by":"publisher","first-page":"2544","DOI":"10.1109\/TPAMI.2011.183","volume":"33","author":"H Yuan","year":"2011","unstructured":"Yuan, H., Atallah, M.J.: Running max\/min filters using 1+o(1) comparisons per sample. IEEE Transactions on Pattern Analysis and Machine Intelligence 33(12), 2544\u20132548 (2011)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21398-9_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T02:27:31Z","timestamp":1676946451000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}