{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:38:02Z","timestamp":1772372282081,"version":"3.50.1"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,3,6]],"date-time":"2018-03-06T00:00:00Z","timestamp":1520294400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"U.S.-Israel Binational Science Foundation","award":["2006\/204"],"award-info":[{"award-number":["2006\/204"]}]},{"name":"U.S.-Israel Binational Science Foundation","award":["2006\/194 and 2012\/229"],"award-info":[{"award-number":["2006\/194 and 2012\/229"]}]},{"DOI":"10.13039\/501100005386","name":"Israeli Centers of Research Excellence (I-CORE) program","doi-asserted-by":"crossref","award":["Center No. 4\/11"],"award-info":[{"award-number":["Center No. 4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Brown University and at MIT"},{"name":"Blavatnik Research Fund in Computer Science at Tel Aviv University"},{"name":"Israel Science Fund","award":["338\/09 and 892\/13"],"award-info":[{"award-number":["338\/09 and 892\/13"]}]},{"name":"Israel Science Fund","award":["794\/13"],"award-info":[{"award-number":["794\/13"]}]},{"name":"Israel Science Fund","award":["822\/10 and 1841\/14"],"award-info":[{"award-number":["822\/10 and 1841\/14"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-0964037, CCF-1111109 and CCR-08-30272"],"award-info":[{"award-number":["CCF-0964037, CCF-1111109 and CCR-08-30272"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Kanellakis fellowship"},{"name":"Hermann Minkowski-MINERVA Center for Geometry at Tel Aviv University"},{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"crossref","award":["1161\/2011"],"award-info":[{"award-number":["1161\/2011"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Israeli ministry of absorption"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"\n We describe a data structure for submatrix maximum queries in Monge matrices or partial Monge matrices, where a query seeks the maximum element in a contiguous submatrix of the given matrix. The structure, for an\n n<\/jats:italic>\n \u00d7\n n<\/jats:italic>\n Monge matrix, takes\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log\n n<\/jats:italic>\n ) space and\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log\n n<\/jats:italic>\n ) preprocessing time, and answers queries in\n O<\/jats:italic>\n (log\n 2<\/jats:sup>\n n<\/jats:italic>\n ) time. For partial Monge matrices, the space grows by \u03b1(\n n<\/jats:italic>\n ), the preprocessing grows by \u03b1(\n n<\/jats:italic>\n )log\n n<\/jats:italic>\n (\u03b1(\n n<\/jats:italic>\n ) is the inverse Ackermann function), and the query remains\n O<\/jats:italic>\n (log\n 2<\/jats:sup>\n n<\/jats:italic>\n ). Our design exploits an interpretation of the column maxima in a Monge (partial Monge, respectively) matrix as an upper envelope of pseudo-lines (pseudo-segments, respectively).\n <\/jats:p>\n \n We give two applications: (1) For a planar set of\n n<\/jats:italic>\n points in an axis-parallel rectangle\n B<\/jats:italic>\n , we build a data structure, in\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \u03b1(\n n<\/jats:italic>\n )log\n 4<\/jats:sup>\n n<\/jats:italic>\n ) time and\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \u03b1(\n n<\/jats:italic>\n )log\n 3<\/jats:sup>\n n<\/jats:italic>\n ) space, that returns, for a query point\n p<\/jats:italic>\n , the largest-area empty axis-parallel rectangle contained in\n B<\/jats:italic>\n and containing\n p<\/jats:italic>\n , in\n O<\/jats:italic>\n (log\n 4<\/jats:sup>\n n<\/jats:italic>\n ) time. This improves substantially the nearly quadratic storage and preprocessing obtained by Augustine et al. [2010]. (2) Given an\n n<\/jats:italic>\n -node arbitrarily weighted planar digraph, with possibly negative edge weights, we build, in\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log\n 2<\/jats:sup>\n n<\/jats:italic>\n \/log log\n n<\/jats:italic>\n ) time, a linear-size data structure that supports edge-weight updates and graph-distance queries between arbitrary pairs of nodes in\n O<\/jats:italic>\n (\n n<\/jats:italic>\n 2\/3<\/jats:sup>\n log\n 5\/3<\/jats:sup>\n n<\/jats:italic>\n ) time per operation. This improves a previous algorithm of Fakcharoenphol and Rao [2006]. Our data structure has already been applied in a recent maximum flow algorithm for planar graphs in Borradaile et al. [2011].\n <\/jats:p>","DOI":"10.1145\/3039873","type":"journal-article","created":{"date-parts":[[2017,3,7]],"date-time":"2017-03-07T14:12:04Z","timestamp":1488895924000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications"],"prefix":"10.1145","volume":"13","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9262-1821","authenticated-orcid":false,"given":"Shay","family":"Mozes","sequence":"additional","affiliation":[{"name":"Interdisciplinary Center, Herzliya, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yahav","family":"Nussbaum","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[{"name":"Tel Aviv University and Courant Institute of Mathematical Sciences, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,3,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90124-U"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840359"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21966"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/41958.41988"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627882"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90071-5"},{"key":"e_1_2_1_7_1","unstructured":"J. Augustine S. Das A. Maheshwari S. C. Nandy S. Roy and S. Sarvattomananda. 2010. Querying for the largest empty geometric object in a desired location. CoRR abs\/1004.0558 (2010)."},{"key":"e_1_2_1_8_1","volume-title":"Proc. 10th Int. Conf. on Pattern Recognit. (ICPR\u201990)","volume":"1","author":"Baird H. S.","unstructured":"H. S. Baird, S. E. Jones, and S. J. Fortune. 1990. Image segmentation by shape-directed covers. In Proc. 10th Int. Conf. on Pattern Recognit. (ICPR\u201990), Vol. 1. 820--825."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/646388.690192"},{"key":"e_1_2_1_10_1","volume-title":"Proc. 13th Canad. Conf. Comput. Geom. (CCCG\u201901)","author":"Boland R. P.","year":"2001","unstructured":"R. P. Boland and J. Urrutia. 2001. Finding the largest axis-aligned rectangle in a polygon in O(n log n) time. In Proc. 13th Canad. Conf. Comput. Geom. (CCCG\u201901). 41--44. http:\/\/www.cccg.ca\/proceedings\/2001\/rboland-876.ps.gz."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.73"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1882123.1882143"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00103-X"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9459-0"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/120864271"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00285-7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215022"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840440"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335359"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/323233.323264"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90112-3"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62559-3_14"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.007"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90328-Q"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_2_1_27_1","volume-title":"Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914)","author":"Gawrychowski P.","unstructured":"P. Gawrychowski, S. Mozes, and O. Weimann. 2014. Improved submatrix maximum queries in Monge matrices. In Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914). 525--537."},{"key":"e_1_2_1_28_1","volume-title":"Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP\u201915)","author":"Gawrychowski P.","unstructured":"P. Gawrychowski, S. Mozes, and O. Weimann. 2015. Submatrix maximum queries in Monge matrices are equivalent to predecessor search. In Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP\u201915). 580--592."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31235-9_21"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90136-1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/007\/0157778"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993679"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321993"},{"key":"e_1_2_1_36_1","first-page":"3","article-title":"Finding the largest disk containing a query point in logarithmic time with linear storage","volume":"6","author":"Kaminker T.","year":"2015","unstructured":"T. Kaminker and M. Sharir. 2015. Finding the largest disk containing a query point in logarithmic time with linear storage. J. Comput. Geom. 6, 2 (2015), 3--18.","journal-title":"J. Comput. Geom."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095147"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1142\/S021819591360008X"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90005-W"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403009"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070454"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488672"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187867"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_2_1_45_1","volume-title":"Proc. 23rd Allerton Conf. Commun. Control Comput. 486--495","author":"McKenna M.","unstructured":"M. McKenna, J. O\u2019Rourke, and S. Suri. 1985. Finding the largest rectangle in an orthogonal polygon. In Proc. 23rd Allerton Conf. Commun. Control Comput. 486--495."},{"key":"e_1_2_1_46_1","unstructured":"G. Monge. 1781. M\u00e9moire sur la th\u00e9orie des d\u00e9blais et des remblais. In Histoire de l\u2019Acad\u00e9mie Royale des Science. 666--704."},{"key":"e_1_2_1_47_1","unstructured":"S. Mozes. 2013. Efficient Algorithms for Shortest-Path and Maximum-Flow Problems in Planar Graphs. Ph.D. Dissertation. Brown University Providence RI."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095135"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1882123.1882147"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90124-0"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/646832.707883"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033190.2033244"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840377"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90012-X"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90118-2"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","unstructured":"M. Sharir and P. K. Agarwal. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press New York NY.","DOI":"10.5555\/235229"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873615"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039873","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3039873","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3039873","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:35:37Z","timestamp":1763458537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039873"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,6]]},"references-count":57,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/3039873"],"URL":"https:\/\/doi.org\/10.1145\/3039873","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,6]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}