{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T02:10:04Z","timestamp":1750299004176,"version":"3.41.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T00:00:00Z","timestamp":1745971200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003134","name":"FRIA","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003134","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Fonds de la Recherche Scientifique-FNRS","award":["MISU F 6001 1"],"award-info":[{"award-number":["MISU F 6001 1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,4,30]]},"abstract":"<jats:p>\n            We give new polynomial lower bounds for a number of dynamic measure problems in computational geometry. These lower bounds hold in the Word RAM model, conditioned on the hardness of 3SUM, APSP, or the Online Matrix-Vector Multiplication problem [Henzinger et al., STOC 2015]. In particular, we get lower bounds in the incremental and fully dynamic settings for counting maximal or extremal points in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb{R}^{3}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , different variants of Klee\u2019s Measure Problem, problems related to finding the largest empty disk in a set of points, and querying the size of the\n            <jats:italic>i<\/jats:italic>\n            th convex layer in a planar set of points. We also answer a question of Chan et al. [SODA 2022] by giving a conditional lower bound for dynamic approximate square set cover. While many conditional lower bounds for dynamic data structures have been proven since the seminal work of P\u0103tra\u015fcu [STOC 2010], few of them relate to computational geometry problems. This is the first article focusing on this topic. Most problems we consider can be solved in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(n\\log n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            time in the static case, and their dynamic versions have only been approached from the perspective of improving known upper bounds. One exception to this is Klee\u2019s measure problem in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb{R}^{2}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , for which Chan [CGTA 2010] gave an unconditional\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Omega(\\sqrt{n})\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            lower bound on the worst-case update time in a variant of the Word RAM machine with large words. By a similar approach, we show that such a lower bound also holds for an important special case of Klee\u2019s measure problem in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb{R}^{3}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            known as the Hypervolume Indicator problem, even for amortized runtime in the incremental setting.\n          <\/jats:p>","DOI":"10.1145\/3727878","type":"journal-article","created":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T18:25:29Z","timestamp":1744136729000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Conditional Lower Bounds for Dynamic Geometric Measure Problems"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5539-9037","authenticated-orcid":false,"given":"Justin","family":"Dallant","sequence":"first","affiliation":[{"name":"Computer Science Department, Universit\u00e9 libre de Bruxelles, Bruxelles, Belgium and Department of Computer Science, Aarhus University, Aarhus, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8885-8172","authenticated-orcid":false,"given":"John","family":"Iacono","sequence":"additional","affiliation":[{"name":"Computer Science Department, Universit\u00e9 libre de Bruxelles, Bruxelles, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2025,5,15]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1109\/FOCS.2016.58","volume-title":"Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS \u201916)","author":"Abboud Amir","year":"2016","unstructured":"Amir Abboud and S\u00f8ren Dahlgaard. 2016. Popular conjectures as a barrier for dynamic planar graph algorithms. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS \u201916). IEEE Computer Society, 477\u2013486. DOI: 10.1109\/FOCS.2016.58"},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1109\/FOCS.2014.53","volume-title":"Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201914)","author":"Abboud Amir","year":"2014","unstructured":"Amir Abboud and Virginia Vassilevska Williams. 2014. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201914). IEEE Computer Society, 434\u2013443. DOI: 10.1109\/FOCS.2014.53"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1050987"},{"key":"e_1_3_3_5_2","first-page":"17","volume-title":"Proceedings of the Algorithms (ESA \u201902)","author":"Agarwal Pankaj K.","year":"2002","unstructured":"Pankaj K. Agarwal, Sathish Govindarajan, and S. Muthukrishnan. 2002. Range searching in categorical data: colored range searching on grid. In Proceedings of the Algorithms (ESA \u201902). Springer Berlin, Berlin, 17\u201328."},{"key":"e_1_3_3_6_2","first-page":"1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP \u201917) (LIPIcs, Vol. 80)","author":"Alman Josh","year":"2017","unstructured":"Josh Alman, Matthias Mnich, and Virginia Vassilevska Williams. 2017. Dynamic parameterized problems and algorithms. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP \u201917) (LIPIcs, Vol. 80). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Article 41, 1\u201316. DOI: 10.4230\/LIPIcs.ICALP.2017.41"},{"key":"e_1_3_3_7_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/978-3-662-43948-7_10","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP \u201914), Part I","volume":"8572","author":"Amir Amihood","year":"2014","unstructured":"Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. 2014. On hardness of jumbled indexing. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP \u201914), Part I. Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.), Lecture Notes in Computer Science, Vol. 8572. Springer, 114\u2013125. DOI: 10.1007\/978-3-662-43948-7_10"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0526-2"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9036-3"},{"key":"e_1_3_3_10_2","first-page":"730","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201916)","author":"Baswana Surender","year":"2016","unstructured":"Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan. 2016. Dynamic DFS in undirected graphs: Breaking the O(m) barrier. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201916), Robert Krauthgamer (Ed.). SIAM, 730\u2013739. DOI: 10.1137\/1.9781611974331.ch52"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1145\/3034786.3034789","volume-title":"Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS \u201917)","author":"Berkholz Christoph","year":"2017","unstructured":"Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2017. Answering conjunctive queries under updates. In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS \u201917). ACM, 303\u2013318. DOI: 10.1145\/3034786.3034789"},{"key":"e_1_3_3_13_2","first-page":"1","volume-title":"Proceedings of the 21st International Conference on Database Theory (ICDT \u201918) (LIPIcs, Vol. 98)","author":"Berkholz Christoph","year":"2018","unstructured":"Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2018. Answering UCQs under updates and in the presence of integrity constraints. In Proceedings of the 21st International Conference on Database Theory (ICDT \u201918) (LIPIcs, Vol. 98). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Article 8, 1\u201319. DOI: 10.4230\/LIPIcs.ICDT.2018.8"},{"key":"e_1_3_3_14_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-3-642-40313-2_20","volume-title":"Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science 2013 (MFCS \u201913)","volume":"8087","author":"Bringmann Karl","year":"2013","unstructured":"Karl Bringmann. 2013. Bringing order to special cases of Klee\u2019s measure problem. In Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science 2013 (MFCS \u201913). Krishnendu Chatterjee and Jir\u00ed Sgall (Eds.), Lecture Notes in Computer Science, Vol. 8087, Springer, 207\u2013218. DOI: 10.1007\/978-3-642-40313-2_20"},{"key":"e_1_3_3_15_2","first-page":"1","volume-title":"Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS \u201919) (LIPIcs, Vol. 126)","author":"Bringmann Karl","year":"2019","unstructured":"Karl Bringmann. 2019. Fine-grained complexity theory (tutorial). In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS \u201919) (LIPIcs, Vol. 126). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Article 4, 1\u20137. DOI: 10.4230\/LIPIcs.STACS.2019.4"},{"key":"e_1_3_3_16_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/978-3-030-80049-9_6","volume-title":"Proceedings of the 17th Conference on Computability in Europe on Connecting with Computability (CiE \u201921), Virtual Event","volume":"12813","author":"Bringmann Karl","year":"2021","unstructured":"Karl Bringmann. 2021. Fine-grained complexity theory: Conditional lower bounds for computational geometry. In Proceedings of the 17th Conference on Computability in Europe on Connecting with Computability (CiE \u201921), Virtual Event. Liesbeth De Mol, Andreas Weiermann, Florin Manea, and David Fern\u00e1ndez-Duque (Eds.), Lecture Notes in Computer Science, Vol. 12813, Springer, 60\u201370. DOI: 10.1007\/978-3-030-80049-9_6"},{"key":"e_1_3_3_17_2","first-page":"1","volume-title":"Proceedings of the 29th Annual European Symposium on Algorithms (ESA \u201921) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 204)","author":"Cardinal Jean","year":"2021","unstructured":"Jean Cardinal, John Iacono, and Grigorios Koumoutsos. 2021. Worst-case efficient dynamic geometric independent set. In Proceedings of the 29th Annual European Symposium on Algorithms (ESA \u201921) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 204). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, Article 25, 1\u201315. DOI: 10.4230\/LIPIcs.ESA.2021.25"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702404389"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.01.007"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-020-00229-5"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3363541"},{"key":"e_1_3_3_22_2","doi-asserted-by":"crossref","first-page":"3496","DOI":"10.1137\/1.9781611977073.139","volume-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chan Timothy M.","year":"2022","unstructured":"Timothy M. Chan, Qizheng He, Subhash Suri, and Jie Xue.2022. Dynamic geometric set cover, revisited. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 3496\u20133528. DOI: 10.1137\/1.9781611977073.139"},{"key":"e_1_3_3_23_2","first-page":"1","volume-title":"Proceedings of the 29th Annual European Symposium on Algorithms (ESA \u201921) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 204)","author":"Chan Timothy M.","year":"2021","unstructured":"Timothy M. Chan and Zhengcheng Huang. 2021. Dynamic colored orthogonal range searching. In Proceedings of the 29th Annual European Symposium on Algorithms (ESA \u201921) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 204). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, Article 28, 1\u201313. DOI: 10.4230\/LIPIcs.ESA.2021.28"},{"key":"e_1_3_3_24_2","first-page":"627","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM)","author":"Chan Timothy M.","year":"2020","unstructured":"Timothy M. Chan and Yakov Nekrich. 2020. Better data structures for colored orthogonal range reporting. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM), 627\u2013636. DOI: 10.1137\/1.9781611975994.38"},{"key":"e_1_3_3_25_2","doi-asserted-by":"crossref","first-page":"1501","DOI":"10.1145\/3519935.3520032","volume-title":"Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201922)","author":"Chan Timothy M.","year":"2022","unstructured":"Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. 2022. Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201922). ACM, 1501\u20131514. DOI: 10.1145\/3519935.3520032"},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1137\/1.9781611977073.10","volume-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chan Timothy M.","year":"2022","unstructured":"Timothy M. Chan and Da Wei Zheng. 2022. Hopcroft\u2019s problem, log-star shaving, 2D fractional cascading, and decision trees. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 190\u2013210. DOI: 10.1137\/1.9781611977073.10"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1985.1057060"},{"key":"e_1_3_3_28_2","first-page":"1","volume-title":"Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT \u201918) (LIPIcs, Vol. 101)","author":"Chen Lijie","year":"2018","unstructured":"Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, and Yuancheng Yu. 2018. Nearly optimal separation between partially and fully retroactive data structures. In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT \u201918) (LIPIcs, Vol. 101). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik. Article 33, 1\u201312. DOI: 10.4230\/LIPIcs.SWAT.2018.33"},{"key":"e_1_3_3_29_2","unstructured":"Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press. Retrieved from http:\/\/mitpress.mit.edu\/books\/introduction-algorithms"},{"key":"e_1_3_3_30_2","first-page":"1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP \u201916) (LIPIcs, Vol. 55)","author":"Dahlgaard S\u00f8ren","year":"2016","unstructured":"S\u00f8ren Dahlgaard. 2016. On the hardness of partially dynamic graph problems and connections to diameter. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP \u201916) (LIPIcs, Vol. 55). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Article 48, 1\u201314. DOI: 10.4230\/LIPIcs.ICALP.2016.48"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3046"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_3_3_34_2","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1109\/FOCS.2014.72","volume-title":"Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201914)","author":"Gr\u00f8nlund Allan","year":"2014","unstructured":"Allan Gr\u00f8nlund and Seth Pettie. 2014. Threesomes, degenerates, and love triangles. In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201914). IEEE Computer Society, 621\u2013630. DOI: 10.1109\/FOCS.2014.72"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453474"},{"key":"e_1_3_3_36_2","first-page":"1042","article-title":"Computational geometry: Generalized (or colored) intersection searching","volume":"67","author":"Gupta Prosenjit","year":"2018","unstructured":"Prosenjit Gupta, Ravi Janardan, Saladi Rahul, and Michiel H. M. Smid. 2018. Computational geometry: Generalized (or colored) intersection searching. In Handbook of Data Structures and Applications (2nd ed.). Dinesh P. Mehta and Sartaj Sahni (Eds.). CRC Press, Chapter 67, 1042\u20131057. Retrieved from https:\/\/www.csa.iisc.ac.in\/~saladi\/Papers\/ds2-handbook.pdf","journal-title":"Handbook of Data Structures and Applications"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1038"},{"key":"e_1_3_3_38_2","first-page":"21","volume-title":"Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC \u201915)","author":"Henzinger Monika","year":"2015","unstructured":"Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. 2015. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC \u201915). ACM, 21\u201330. DOI: 10.1145\/2746539.2746609"},{"key":"e_1_3_3_39_2","first-page":"1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS \u201917) (LIPIcs, Vol. 67)","author":"Henzinger Monika","year":"2017","unstructured":"Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. 2017. Conditional hardness for sensitivity problems. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS \u201917) (LIPIcs, Vol. 67). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Article 26, 1\u201331. DOI: 10.4230\/LIPIcs.ITCS.2017.26"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1142\/S021819599300004X"},{"key":"e_1_3_3_41_2","doi-asserted-by":"crossref","first-page":"1515","DOI":"10.1145\/3519935.3520036","volume-title":"Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201922)","author":"Jin Ce","year":"2022","unstructured":"Ce Jin and Yinzhan Xu. 2022. Tight dynamic problem lower bounds from generalized BMM and OMv. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201922), 1515\u20131528. DOI: 10.1145\/3519935.3520036"},{"key":"e_1_3_3_42_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1007\/978-3-319-21840-3_38","volume-title":"Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS \u201915)","volume":"9214","author":"Karczmarz Adam","year":"2015","unstructured":"Adam Karczmarz and Jakub Lacki. 2015. Fast and simple connectivity in graph timelines. In Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS \u201915). Frank Dehne, J\u00f6rg-R\u00fcdiger Sack, and Ulrike Stege (Eds.), Lecture Notes in Computer Science, Vol. 9214, Springer, 458\u2013469. DOI: 10.1007\/978-3-319-21840-3_38"},{"key":"e_1_3_3_43_2","unstructured":"Young Kun Ko and Min Jae Song. 2020. Hardness of approximate nearest neighbor search under L-infinity. arXiv:2011.06135. Retrieved from https:\/\/arxiv.org\/abs\/2011.06135"},{"key":"e_1_3_3_44_2","first-page":"1","volume-title":"Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM \u201916) (LIPIcs, Vol. 54)","author":"Kopelowitz Tsvi","year":"2016","unstructured":"Tsvi Kopelowitz and Robert Krauthgamer. 2016. Color-distance oracles and snippets. In Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM \u201916) (LIPIcs, Vol. 54). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Article 24, 1\u201310. DOI: 10.4230\/LIPIcs.CPM.2016.24"},{"key":"e_1_3_3_45_2","first-page":"1272","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201916)","author":"Kopelowitz Tsvi","year":"2016","unstructured":"Tsvi Kopelowitz, Seth Pettie, and Ely Porat. 2016. Higher lower bounds from the 3SUM conjecture. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201916). SIAM, 1272\u20131287. DOI: 10.1137\/1.9781611974331.ch89"},{"key":"e_1_3_3_46_2","first-page":"265","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Larsen Kasper Green","year":"2013","unstructured":"Kasper Green Larsen and Freek van Walderveen. 2013. Near-Optimal range reporting structures for categorical data. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 265\u2013276. DOI: 10.1137\/1.9781611973105.20"},{"key":"e_1_3_3_47_2","first-page":"2182","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201917)","author":"Larsen Kasper Green","year":"2017","unstructured":"Kasper Green Larsen and R. Ryan Williams. 2017. Faster online matrix-vector multiplication. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201917). SIAM, 2182\u20132189. DOI: 10.1137\/1.9781611974782.142"},{"key":"e_1_3_3_48_2","first-page":"1","volume-title":"Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS \u201921) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 185)","author":"Lau Joshua","year":"2021","unstructured":"Joshua Lau and Angus Ritossa. 2021. Algorithms and hardness for multidimensional range updates and queries. In Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS \u201921) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 185). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, Article 35, 1\u201320. DOI: 10.4230\/LIPIcs.ITCS.2021.35"},{"key":"e_1_3_3_49_2","volume-title":"Generalized Static Orthogonal Range Searching in Less Space","author":"Mortensen Christian W.","year":"2003","unstructured":"Christian W. Mortensen. 2003. Generalized Static Orthogonal Range Searching in Less Space. Technical Report TR-2003-33. IT University of Copenhagen, Copenhagen, Denmark."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/2543924"},{"key":"e_1_3_3_51_2","volume-title":"Searching in the past II: General Transforms","author":"Overmars Mark H.","year":"1981","unstructured":"Mark H. Overmars. 1981. Searching in the past II: General Transforms. Technical Report RUU-CS-81-9. Department of Computer Science, University of Utrecht, Utrecht, The Netherlands."},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90012-X"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/0220065"},{"key":"e_1_3_3_54_2","first-page":"1","volume-title":"Proceedings of the 26th Annual European Symposium on Algorithms (ESA \u201918) (LIPIcs, Vol. 112)","author":"Probst Maximilian","year":"2018","unstructured":"Maximilian Probst. 2018. On the complexity of the (approximate) nearest colored node problem. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA \u201918) (LIPIcs, Vol. 112). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Article 68, 1\u201314. DOI: 10.4230\/LIPIcs.ESA.2018.68"},{"key":"e_1_3_3_55_2","first-page":"603","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC \u201910)","author":"P\u0103tra\u015fcu Mihai","year":"2010","unstructured":"Mihai P\u0103tra\u015fcu. 2010. Towards polynomial lower bounds for dynamic problems. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC \u201910). ACM, New York, NY, 603\u2013610. DOI: 10.1145\/1806689.1806772"},{"key":"e_1_3_3_56_2","doi-asserted-by":"crossref","first-page":"1260","DOI":"10.1145\/3188745.3188916","volume-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201918)","author":"Rubinstein Aviad","year":"2018","unstructured":"Aviad Rubinstein. 2018. Hardness of approximate nearest neighbor search. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201918). ACM, 1260\u20131268. DOI: 10.1145\/3188745.3188916"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.04.008"},{"key":"e_1_3_3_58_2","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1109\/FOCS.2019.00036","volume-title":"Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201919)","author":"van den Brand Jan","year":"2019","unstructured":"Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. 2019. Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds. In Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201919). IEEE Computer Society, 456\u2013480. DOI: 10.1109\/FOCS.2019.00036"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1024524"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1142\/9789813272880_0188"},{"key":"e_1_3_3_61_2","first-page":"786","volume-title":"Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201920)","author":"Williams Virginia Vassilevska","year":"2020","unstructured":"Virginia Vassilevska Williams and Yinzhan Xu. 2020. Monochromatic triangles, triangle listing and APSP. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201920). IEEE, 786\u2013797. DOI: 10.1109\/FOCS46700.2020.00078"},{"key":"e_1_3_3_62_2","volume-title":"Proceedings of the 23rd Annual Canadian Conference on Computational Geometry","author":"Yildiz Hakan","year":"2011","unstructured":"Hakan Yildiz, John Hershberger, and Subhash Suri. 2011. A discrete and dynamic version of Klee\u2019s measure problem. In Proceedings of the 23rd Annual Canadian Conference on Computational Geometry. Retrieved from http:\/\/www.cccg.ca\/proceedings\/2011\/papers\/paper28.pdf"},{"key":"e_1_3_3_63_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/978-3-642-23719-5_50","volume-title":"Proceedings of the 19th Annual European Symposium on Algorithms (ESA \u201911)","volume":"6942","author":"Y\u0131ld\u0131z Hakan","year":"2011","unstructured":"Hakan Y\u0131ld\u0131z, Luca Foschini, John Hershberger, and Subhash Suri. 2011. The union of probabilistic boxes: Maintaining the volume. In Proceedings of the 19th Annual European Symposium on Algorithms (ESA \u201911). Camil Demetrescu and Magn\u00fas M. Halld\u00f3rsson (Eds.), Lecture Notes in Computer Science, Vol. 6942. Springer, 591\u2013602. DOI: 10.1007\/978-3-642-23719-5_50"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727878","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3727878","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:57:24Z","timestamp":1750298244000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727878"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,30]]},"references-count":62,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1145\/3727878"],"URL":"https:\/\/doi.org\/10.1145\/3727878","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,4,30]]},"assertion":[{"value":"2023-10-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-04","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}