{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T21:46:53Z","timestamp":1768340813251,"version":"3.49.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,4,18]],"date-time":"2023-04-18T00:00:00Z","timestamp":1681776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFF (Det Frie Forskningsr\u00e5d) of Danish Council for Independent Research","award":["DFF-7014-00404"],"award-info":[{"award-number":["DFF-7014-00404"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"\n In the semialgebraic range searching problem, we are given a set of\n n<\/jats:italic>\n points in \u211d\n \n d<\/jats:italic>\n <\/jats:sup>\n , and we want to preprocess the points such that for any query range belonging to a family of constant complexity semialgebraic sets (Tarski cells), all the points intersecting the range can be reported or counted efficiently. When the ranges are composed of simplices, the problem is well-understood: It can be solved using\n S(n)<\/jats:italic>\n space and with\n Q(n)<\/jats:italic>\n query time with\n \n \\(S(n)Q(n)^d = \\tilde{O}(n^d),\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n where the\n \n \\(\\tilde{O}(\\cdot)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n notation hides polylogarithmic factors and this trade-off is tight (up to\n n<\/jats:italic>\n \n o<\/jats:italic>\n (1)\n <\/jats:sup>\n factors). In particular, there exist \u201clow space\u201d structures that use\n O(n)<\/jats:italic>\n space with\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \n 1-1\/\n d<\/jats:italic>\n }\n <\/jats:sup>\n ) query time\u00a0[\n 8<\/jats:xref>\n ,\n 25<\/jats:xref>\n ] and \u201cfast query\u201d structures that use\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \n d<\/jats:italic>\n <\/jats:sup>\n ) space with\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n ) query time\u00a0[\n 9<\/jats:xref>\n ]. However, for general semialgebraic ranges, only \u201clow space\u201d solutions are known, but the best solutions\u00a0[\n 7<\/jats:xref>\n ] match the same trade-off curve as simplex queries, with\n O<\/jats:italic>\n (\n n<\/jats:italic>\n ) space and\n \n \\(\\tilde{O}(n^{1-1\/d})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n query time. It has been conjectured that the same could be done for the \u201cfast query\u201d case, but this open problem has stayed unresolved.\n <\/jats:p>\n \n Here, we disprove this conjecture. We give the first nontrivial lower bounds for semialgebraic range searching and other related problems. More precisely, we show that any data structure for reporting the points between two concentric circles, a problem that we call 2D annulus reporting, with\n Q<\/jats:italic>\n (\n n<\/jats:italic>\n ) query time must use\n \n \\(S(n)=\\overset{\\scriptscriptstyle o}{\\Omega }(n^3\/Q(n)^5)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n space, where the\n \n \\(\\overset{\\scriptscriptstyle o}{\\Omega }(\\cdot)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n notation hides\n \n \\(n^{o(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n factors, meaning, for\n \n \\(Q(n)=\\log ^{O(1)}n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n \n \\(\\overset{\\scriptscriptstyle o}{\\Omega }(n^3)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n space must be used. In addition, we study the problem of reporting the subset of input points in a polynomial slab defined by\n \n \\(\\lbrace (x,y)\\in \\mathbb {R}^2:P(x)\\le y\\le P(x)+w\\rbrace\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where\n \n \\(P(x)=\\sum _{i=0}^\\Delta a_i x^i\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is a univariate polynomial of degree \u0394 and\n \n \\(a_0, \\ldots , a_\\Delta , w\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n are given at the query time, a problem that we call polynomial slab reporting. For this, we show a space lower bound of\n \n \\(\\overset{\\scriptscriptstyle o}{\\Omega }(n^{\\Delta +1}\/Q(n)^{(\\Delta +3)\\Delta \/2})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , which implies that for\n \n \\(Q(n)=\\log ^{O(1)}n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , we must use\n \n \\(\\overset{\\scriptscriptstyle o}{\\Omega }(n^{\\Delta +1})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n space. We also consider the dual semialgebraic stabbing problems of semialgebraic range searching and present lower bounds for them. In particular, we show that in linear space, any data structure that solves 2D annulus stabbing problems must use\n \n \\(\\Omega (n^{2\/3})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n query time. Note that this almost matches the upper bound obtained by lifting 2D annuli to 3D. Like semialgebraic range searching, we also present lower bounds for general polynomial slab stabbing problems. Again, our lower bounds are almost tight for linear size data structures in this case.\n <\/jats:p>","DOI":"10.1145\/3578574","type":"journal-article","created":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T13:55:10Z","timestamp":1672754110000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Lower Bounds for Semialgebraic Range Searching and Stabbing Problems"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6102-0759","authenticated-orcid":false,"given":"Peyman","family":"Afshani","sequence":"first","affiliation":[{"name":"Aarhus University, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8131-847X","authenticated-orcid":false,"given":"Pingan","family":"Cheng","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2023,4,18]]},"reference":[{"key":"e_1_3_4_2_2","first-page":"339","volume-title":"Proceedings of the 28th Annual Symposium on Computational Geometry (SoCG\u201912)","author":"Afshani Peyman","year":"2012","unstructured":"Peyman Afshani. 2012. Improved pointer machine and I\/O lower bounds for simplex range reporting and related problems. In Proceedings of the 28th Annual Symposium on Computational Geometry (SoCG\u201912). ACM, New York, NY, 339\u2013346. 10.1145\/2261250.2261301"},{"key":"e_1_3_4_3_2","doi-asserted-by":"crossref","unstructured":"Peyman Afshani and Pingan Cheng. 2022. An optimal lower bound for simplex range reporting. Retrieved from https:\/\/arXiv:2210.14736.","DOI":"10.1137\/1.9781611977585.ch25"},{"key":"e_1_3_4_4_2","first-page":"898","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Afshani Peyman","year":"2018","unstructured":"Peyman Afshani and Anne Driemel. 2018. On the complexity of range searching among curves. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA, 898\u2013917. 10.1137\/1.9781611975031.58"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-44479-6_1"},{"key":"e_1_3_4_6_2","series-title":"Proceedings of the 35th International Symposium on Computational Geometry","first-page":"Art. No. 5, 14","volume":"129","author":"Agarwal Pankaj K.","year":"2019","unstructured":"Pankaj K. Agarwal, Boris Aronov, Esther Ezra, and Joshua Zahl. 2019. An efficient algorithm for generalized polynomial partitioning and its applications. In Proceedings of the 35th International Symposium on Computational Geometry. LIPIcs. Leibniz Int. Proc. Inform., Vol. 129. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Art. No. 5, 14."},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574015"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/120890855"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9410-z"},{"key":"e_1_3_4_10_2","unstructured":"Timothy M. Chan and Da Wei Zheng. 2022. Simplex range searching revisited: How to shave logs in multi-level data structures. Retrieved from https:\/\/arXiv:2210.10172."},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.2307\/1990891"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77614"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189314"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781315119335"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122778"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00002-X"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187743"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187879"},{"key":"e_1_3_4_19_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"Berg Mark de","year":"2008","unstructured":"Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. 2008. Computational Geometry: Algorithms and Applications, 3rd ed. Springer. Retrieved from https:\/\/www.worldcat.org\/oclc\/227584184."},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00607-3"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781315119601"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004115000468"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2015.181.1.2"},{"key":"e_1_3_4_24_2","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/10515.10522","volume-title":"Proceedings of the 2nd Annual Symposium on Computational Geometry (SCG\u201986)","author":"Haussler D.","year":"1986","unstructured":"D. Haussler and E. Welzl. 1986. Epsilon-nets and simplex range queries. In Proceedings of the 2nd Annual Symposium on Computational Geometry (SCG\u201986). ACM, New York, NY, 61\u201371. DOI:10.1145\/10515.10522"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574697"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573972"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9701-2"},{"key":"e_1_3_4_28_2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/73393.73397","volume-title":"Proceedings of the 4th Annual Symposium on Computational Geometry","author":"Welzl Emo","year":"1988","unstructured":"Emo Welzl. 1988. Partition trees for triangle counting and other range searching problems. In Proceedings of the 4th Annual Symposium on Computational Geometry. ACM, New York, 23\u201333. DOI:10.1145\/73393.73397"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211012"},{"key":"e_1_3_4_30_2","first-page":"163","volume-title":"Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC\u201985)","author":"Yao A. C.","year":"1985","unstructured":"A. C. Yao and F. F. Yao. 1985. A general approach to D-Dimensional geometric queries. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC\u201985). ACM, New York, NY, 163\u2013168. DOI:10.1145\/22145.22163"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3578574","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3578574","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:37Z","timestamp":1750183717000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3578574"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,18]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3578574"],"URL":"https:\/\/doi.org\/10.1145\/3578574","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,18]]},"assertion":[{"value":"2021-04-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}