{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:33:58Z","timestamp":1787340838139,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>In this paper we establish an intimate connection between dynamic range searching in the group model and combinatorial discrepancy. Our result states that, for a broad class of range searching data structures (including all known upper bounds), it must hold that $t_u t_q=\\Omega(\\mbox{disc}^2)$, where $t_u$ is the worst case update time, $t_q$ is the worst case query time, and disc is the combinatorial discrepancy of the range searching problem in question. This relation immediately implies a whole range of exceptionally high and near-tight lower bounds for all of the basic range searching problems. We list a few of them in the following: (1) For $d$-dimensional halfspace range searching, we get a lower bound of $t_u t_q=\\Omega(n^{1-1\/d})$. This comes within an lg lg $n$ factor of the best known upper bound. (2) For orthogonal range searching, we get a lower bound of $t_u t_q=\\Omega(\\mbox{lg}^{d-1}n)$. (3) For ball range searching, we get a lower bound of $t_u t_q=\\Omega(n^{1-1\/d})$. We note that the previous highest lower bound for any explicit problem, due to P\u01cetra\u015fcu [Proceedings of the 39th ACM Symposium on Theory of Computation, 2007, pp. 40--46], states that $t_q=\\Omega((\\mbox{lg} n\/\\mbox{lg}(\\mbox{lg} n+t_u))^2)$, which does, however, hold for a less restrictive class of data structures. Our result also has implications for the field of combinatorial discrepancy. Using textbook range searching solutions, we improve on the best known discrepancy upper bound for axis-aligned rectangles in all dimensions $d\\ge 3$.<\/jats:p>","DOI":"10.1137\/120865240","type":"journal-article","created":{"date-parts":[[2014,4,29]],"date-time":"2014-04-29T12:51:46Z","timestamp":1398775906000},"page":"673-686","source":"Crossref","is-referenced-by-count":13,"title":["On Range Searching in the Group Model and Combinatorial Discrepancy"],"prefix":"10.1137","volume":"43","author":[{"given":"Kasper Green","family":"Larsen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,4,29]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02123006"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199807)12:4<351::AID-RSA3>3.0.CO;2-S"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"N. Bansal,\n                      Constructive algorithms for discrepancy minimization\n                      , in Proceedings of the 51st IEEE Symposium on Foundations of Computer Science, 2010, pp. 3-10.","DOI":"10.1109\/FOCS.2010.7"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579453"},{"key":"atypb5","first-page":"63","author":"Beck J.","year":"1988","journal-title":"Amsterdam"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90022-6"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196138"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358850"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2007.09.010"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"T. M. Chan,\n                      Optimal partition trees\n                      , in Proceedings of the 26th ACM Symposium on Computational Geometry, 2010, pp. 1-10.","DOI":"10.1145\/1810959.1810961"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"B. Chazelle,\n                      Lower bounds for off-line range searching\n                      , in Proceedings of the 27th ACM Symposium on Theory of Computation, 1995, pp. 733-740.","DOI":"10.1145\/225058.225291"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794275665"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"B. Chazelle,\n                      The Discrepancy Method: Randomness and Complexity\n                      , Cambridge University Press, Cambridge, UK, 2000.","DOI":"10.1017\/CBO9780511626371"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"B. Chazelle and A. Lvov,\n                      A trace bound for the hereditary discrepancy\n                      , in Proceedings of the 16th ACM Symposium on Computational Geometry, 2000, pp. 64-69.","DOI":"10.1145\/336154.336179"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322305"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"M. L. Fredman and M. Saks,\n                      The cell probe complexity of dynamic data structures\n                      , in Proceedings of the 21st ACM Symposium on Theory of Computation, 1989, pp. 345-354.","DOI":"10.1145\/73007.73040"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574066"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek,\n                      Geometric Discrepancy\n                      , Springer, Berlin, 1999.","DOI":"10.1007\/978-3-642-03942-3"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293051"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"M. P\u01cetra\u015fcu,\n                      Lower bounds for $2$-dimensional range counting\n                      , in Proceedings of the 39th ACM Symposium on Theory of Computation, 2007, pp. 40-46.","DOI":"10.1145\/1250790.1250797"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447256"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300000541"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.4064\/aa-9-3-257-260"},{"key":"atypb24","first-page":"692","author":"Srinivasan A.","year":"1997","journal-title":"Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120865240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:51:20Z","timestamp":1787338280000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120865240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/120865240"],"URL":"https:\/\/doi.org\/10.1137\/120865240","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}