{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T17:00:35Z","timestamp":1759683635878,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,4,30]],"date-time":"2018-04-30T00:00:00Z","timestamp":1525046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"HKRGC","award":["GRF-16211614, GRF-16200415 and GRF-16202317"],"award-info":[{"award-number":["GRF-16211614, GRF-16200415 and GRF-16202317"]}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Research Funds of Renmin University of China","award":["18XNLG21"],"award-info":[{"award-number":["18XNLG21"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61502503"],"award-info":[{"award-number":["61502503"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,4,30]]},"abstract":"<jats:p>\n            We study the problem of two-dimensional orthogonal range counting with additive error. Given a set\n            <jats:italic>P<\/jats:italic>\n            of\n            <jats:italic>n<\/jats:italic>\n            points drawn from an\n            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            grid and an error parameter \u03b5, the goal is to build a data structure, such that for any orthogonal range\n            <jats:italic>R<\/jats:italic>\n            , it can return the number of points in\n            <jats:italic>P<\/jats:italic>\n            \u2229\n            <jats:italic>R<\/jats:italic>\n            with additive error \u03b5\n            <jats:italic>n<\/jats:italic>\n            . A well-known solution for this problem is obtained by using\n            <jats:italic>\u03b5-approximation<\/jats:italic>\n            , which is a subset\n            <jats:italic>A<\/jats:italic>\n            \u2286\n            <jats:italic>P<\/jats:italic>\n            that can estimate the number of points in\n            <jats:italic>P<\/jats:italic>\n            \u2229\n            <jats:italic>R<\/jats:italic>\n            with the number of points in\n            <jats:italic>A<\/jats:italic>\n            \u2229\n            <jats:italic>R<\/jats:italic>\n            . It is known that an \u03b5-approximation of size\n            <jats:italic>O<\/jats:italic>\n            (1\/\u03b5 log\n            <jats:sup>2.5<\/jats:sup>\n            1\/\u03b5) exists for any\n            <jats:italic>P<\/jats:italic>\n            with respect to orthogonal ranges, and the best lower bound is \u03a9(1\/\u03b5 log 1\/\u03b5).\n          <\/jats:p>\n          <jats:p>\n            The \u03b5-approximation is a rather restricted data structure, as we are not allowed to store any information other than the coordinates of the points. In this article, we explore what can be achieved without any restriction on the data structure. We first describe a simple data structure that uses\n            <jats:italic>O<\/jats:italic>\n            (1\/\u03b5(log\n            <jats:sup>2<\/jats:sup>\n            1\/\u03b5 + log\n            <jats:italic>n<\/jats:italic>\n            )) bits and answers queries with error \u03b5\n            <jats:italic>n<\/jats:italic>\n            . We then prove a lower bound that any data structure that answers queries with error \u03b5\n            <jats:italic>n<\/jats:italic>\n            will have to use \u03a9(1\/\u03b5 (log\n            <jats:sup>2<\/jats:sup>\n            1\/\u03b5 + log\n            <jats:italic>n<\/jats:italic>\n            )) bits. Our lower bound is information-theoretic: We show that there is a collection of 2\n            <jats:sup>\u03a9<\/jats:sup>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) point sets with large\n            <jats:italic>union combinatorial discrepancy<\/jats:italic>\n            and thus are hard to distinguish unless we use \u03a9(\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) bits.\n          <\/jats:p>","DOI":"10.1145\/3205454","type":"journal-article","created":{"date-parts":[[2018,6,4]],"date-time":"2018-06-04T13:41:34Z","timestamp":1528119694000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Tight Space Bounds for Two-Dimensional Approximate Range Counting"],"prefix":"10.1145","volume":"14","author":[{"given":"Zhewei","family":"Wei","sequence":"first","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"HKUST, Clear Water Bay, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116258.3116371"},{"key":"e_1_2_1_2_1","unstructured":"P. K. Agarwal and J. Erickson. 1997. Geometric range searching and its relatives. In Discrete and Computational Geometry: Ten Years Later. Mathematical Society Press.   P. K. Agarwal and J. Erickson. 1997. Geometric range searching and its relatives. In Discrete and Computational Geometry: Ten Years Later. Mathematical Society Press."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/090762968"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/080736600"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(00)00022-5"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579453"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90022-6"},{"volume-title":"The Discrepancy Method","author":"Chazelle B.","key":"e_1_2_1_9_1","unstructured":"B. Chazelle . 2000. The Discrepancy Method . Cambridge University Press . B. Chazelle. 2000. The Discrepancy Method. Cambridge University Press."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1520-6610(1999)7:5<381::AID-JCD7>3.0.CO;2-S"},{"key":"e_1_2_1_12_1","unstructured":"M. Darnall. 2008. Results on Low Discrepancy Point Sets. ProQuest.  M. Darnall. 2008. Results on Low Discrepancy Point Sets. ProQuest."},{"key":"e_1_2_1_13_1","first-page":"79","article-title":"On Roth\u2019s method in the theory of irregularities of point distributions Recent Progr","volume":"2","author":"Hal\u00e1sz G.","year":"1981","unstructured":"G. Hal\u00e1sz . 1981 . On Roth\u2019s method in the theory of irregularities of point distributions Recent Progr . Analytic Number Theory 2 : 79 -- 94 . G. Hal\u00e1sz. 1981. On Roth\u2019s method in the theory of irregularities of point distributions Recent Progr. Analytic Number Theory 2: 79--94.","journal-title":"Analytic Number Theory"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1966749.1966753"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187876"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"P. Hellekalek G. Larcher and J. Beck. 1998. Random and Quasi-Random Point Sets. Vol. 138. Springer Verlag.  P. Hellekalek G. Larcher and J. Beck. 1998. Random and Quasi-Random Point Sets. Vol. 138. Springer Verlag.","DOI":"10.1007\/978-1-4612-1702-2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.14"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.23"},{"volume-title":"Proceedings of the International Symposium on Computational Geometry. 1--15","author":"Matou\u0161ek J.","key":"e_1_2_1_19_1","unstructured":"J. Matou\u0161ek , and A. Nikolov . 2015. Combinatorial discrepancy for boxes via the \u03b3<sub>2<\/sub> Norm . In Proceedings of the International Symposium on Computational Geometry. 1--15 . J. Matou\u0161ek, and A. Nikolov. 2015. Combinatorial discrepancy for boxes via the \u03b3<sub>2<\/sub> Norm. In Proceedings of the International Symposium on Computational Geometry. 1--15."},{"volume-title":"Geometric Discrepancy","author":"Matou\u0161ek J.","key":"e_1_2_1_20_1","unstructured":"J. Matou\u0161ek . 1999. Geometric Discrepancy . Springer , Heidelberg, Germany . J. Matou\u0161ek. 1999. Geometric Discrepancy. Springer, Heidelberg, Germany."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2012-00759-0"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300000541"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0017089500006182"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4064\/aa-21-1-45-50"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"I. Sobol. 1967. On the distribution of points in a cube and the approximate evaluation of integrals. Zhurnal Vychislitel\u2019noi Matematiki i Matematicheskoi Fiziki 7(4): 784--802.  I. Sobol. 1967. On the distribution of points in a cube and the approximate evaluation of integrals. Zhurnal Vychislitel\u2019noi Matematiki i Matematicheskoi Fiziki 7(4): 784--802.","DOI":"10.1016\/0041-5553(67)90144-9"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 692--701","author":"Srinivasan A.","year":"1997","unstructured":"A. Srinivasan . 1997 . Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 692--701 . A. Srinivasan. 1997. Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 692--701."},{"key":"e_1_2_1_27_1","unstructured":"J. Van der Corput. 1936. Verteilungsfunktionen. NV Noord-Hollandsche Uitgevers Maatschappij.  J. Van der Corput. 1936. Verteilungsfunktionen. NV Noord-Hollandsche Uitgevers Maatschappij."},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 252--264","author":"Wei Z.","key":"e_1_2_1_28_1","unstructured":"Z. Wei and K. Yi . 2013. The space complexity of two-dimensional approximate range counting . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 252--264 . Z. Wei and K. Yi. 2013. The space complexity of two-dimensional approximate range counting. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 252--264."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3205454","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3205454","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:55Z","timestamp":1750208935000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3205454"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,30]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4,30]]}},"alternative-id":["10.1145\/3205454"],"URL":"https:\/\/doi.org\/10.1145\/3205454","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,4,30]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}