{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T11:02:09Z","timestamp":1768734129433,"version":"3.49.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,2,28]],"date-time":"2012-02-28T00:00:00Z","timestamp":1330387200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00454-012-9412-x","type":"journal-article","created":{"date-parts":[[2012,2,27]],"date-time":"2012-02-27T09:35:57Z","timestamp":1330335357000},"page":"711-730","source":"Crossref","is-referenced-by-count":10,"title":["Tight Lower Bounds for Halfspace Range Searching"],"prefix":"10.1007","volume":"47","author":[{"given":"Sunil","family":"Arya","sequence":"first","affiliation":[]},{"given":"David M.","family":"Mount","sequence":"additional","affiliation":[]},{"given":"Jian","family":"Xia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,2,28]]},"reference":[{"key":"9412_CR1","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/conm\/223\/03131","volume-title":"Advances in Discrete and Computational Geometry","author":"P.K. Agarwal","year":"1999","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Advances in Discrete and Computational Geometry. Contemporary Mathematics, vol. 223, pp. 1\u201356. American Mathematical Society, Providence (1999)"},{"key":"9412_CR2","first-page":"564","volume-title":"Proc. 38th Annu. ACM Sympos. Theory Comput.","author":"S. Arya","year":"2006","unstructured":"Arya, S., Malamatos, T., Mount, D.M.: On the importance of idempotence. In: Proc. 38th Annu. ACM Sympos. Theory Comput., pp. 564\u2013573 (2006)"},{"issue":"3","key":"9412_CR3","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1007\/s00454-009-9140-z","volume":"41","author":"S. Arya","year":"2009","unstructured":"Arya, S., Malamatos, T., Mount, D.M.: The effect of corners on the complexity of approximate range searching. Discrete Comput. Geom. 41(3), 398\u2013443 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"9412_CR4","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/BF02573971","volume":"10","author":"H. Br\u00f6nnimann","year":"1993","unstructured":"Br\u00f6nnimann, H., Chazelle, B., Pach, J.: How hard is halfspace range searching? Discrete Comput. Geom. 10, 143\u2013155 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9412_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1810959.1810961","volume-title":"Proc. 26th Annu. ACM Sympos. Comput. Geom.","author":"T.M. Chan","year":"2010","unstructured":"Chan, T.M.: Optimal partition trees. In: Proc. 26th Annu. ACM Sympos. Comput. Geom., pp. 1\u201310 (2010)"},{"key":"9412_CR6","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1090\/S0894-0347-1989-1001852-0","volume":"2","author":"B. Chazelle","year":"1989","unstructured":"Chazelle, B.: Lower bounds on the complexity of polytope range searching. J. Am. Math. Soc. 2, 637\u2013666 (1989)","journal-title":"J. Am. Math. Soc."},{"key":"9412_CR7","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1145\/79147.79149","volume":"37","author":"B. Chazelle","year":"1990","unstructured":"Chazelle, B.: Lower bounds for orthogonal range searching, II: The arithmetic model. J. Assoc. Comput. Mach. 37, 439\u2013463 (1990)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9412_CR8","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF01758854","volume":"8","author":"B. Chazelle","year":"1992","unstructured":"Chazelle, B., Sharir, M., Welzl, E.: Quasi-optimal upper bounds for simplex range searching and new zone theorems. Algorithmica 8, 407\u2013429 (1992)","journal-title":"Algorithmica"},{"issue":"5","key":"9412_CR9","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02187743","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"Chazelle, B., Welzl, E.: Quasi-optimal range searching in spaces of finite VC-dimension. Discrete Comput. Geom. 4(5), 467\u2013489 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9412_CR10","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/j.comgeo.2008.09.009","volume":"43","author":"G.D. Fonseca da","year":"2009","unstructured":"da Fonseca, G.D., Mount, D.M.: Approximate range searching: The absolute model. Comput. Geom. 43(4), 434\u2013444 (2009)","journal-title":"Comput. Geom."},{"key":"9412_CR11","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s00453-002-0961-x","volume":"34","author":"M. Berg de","year":"2002","unstructured":"de Berg, M., Katz, M.J., van\u00a0der Stappen, A.F., Vleugels, J.: Realistic input models for geometric algorithms. Algorithmica 34, 81\u201397 (2002)","journal-title":"Algorithmica"},{"issue":"6","key":"9412_CR12","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0020-0190(86)90088-8","volume":"23","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Welzl, E.: Halfplanar range search in linear space and O(n 0.695) query time. Inf. Process. Lett. 23(6), 289\u2013293 (1986)","journal-title":"Inf. Process. Lett."},{"key":"9412_CR13","doi-asserted-by":"crossref","first-page":"1968","DOI":"10.1137\/S0097539798337212","volume":"29","author":"J. Erickson","year":"2000","unstructured":"Erickson, J.: Space-time tradeoffs for emptiness queries. SIAM J. Comput. 29, 1968\u20131996 (2000)","journal-title":"SIAM J. Comput."},{"key":"9412_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0210001","volume":"10","author":"M.L. Fredman","year":"1981","unstructured":"Fredman, M.L.: Lower bounds on the complexity of some optimal data structures. SIAM J. Comput. 10, 1\u201310 (1981)","journal-title":"SIAM J. Comput."},{"key":"9412_CR15","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol. 2, 2nd edn. Springer, Berlin (1993)","edition":"2"},{"key":"9412_CR16","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"9412_CR17","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J.: Range searching with efficient hierarchical cuttings. Discrete Comput. Geom. 10(2), 157\u2013182 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9412_CR18","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1145\/197405.197408","volume":"26","author":"J. Matou\u0161ek","year":"1994","unstructured":"Matou\u0161ek, J.: Geometric range searching. ACM Comput. Surv. 26, 421\u2013461 (1994)","journal-title":"ACM Comput. Surv."},{"key":"9412_CR19","first-page":"124","volume-title":"Proc. 5th Annu. ACM Sympos. Comput. Geom.","author":"J. Matou\u0161ek","year":"1989","unstructured":"Matou\u0161ek, J., Welzl, E.: Good splitters for counting points in triangles. In: Proc. 5th Annu. ACM Sympos. Comput. Geom., pp. 124\u2013130 (1989)"},{"key":"9412_CR20","first-page":"23","volume-title":"Proc. 4th Annu. ACM Sympos. Comput. Geom.","author":"E. Welzl","year":"1988","unstructured":"Welzl, E.: Partition trees for triangle counting and other range searching problems. In: Proc. 4th Annu. ACM Sympos. Comput. Geom., pp. 23\u201333 (1988)"},{"key":"9412_CR21","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1137\/0211012","volume":"11","author":"D.E. Willard","year":"1982","unstructured":"Willard, D.E.: Polygon retrieval. SIAM J. Comput. 11, 149\u2013165 (1982)","journal-title":"SIAM J. Comput."},{"key":"9412_CR22","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0214022","volume":"14","author":"A.C. Yao","year":"1985","unstructured":"Yao, A.C.: On the complexity of maintaining partial sums. SIAM J. Comput. 14, 277\u2013288 (1985)","journal-title":"SIAM J. Comput."},{"key":"9412_CR23","first-page":"258","volume-title":"Proc. 15th Annu. ACM Sympos. Theory Comput.","author":"F.F. Yao","year":"1983","unstructured":"Yao, F.F.: A 3-space partition and its applications. In: Proc. 15th Annu. ACM Sympos. Theory Comput., pp. 258\u2013263 (1983)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9412-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-012-9412-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9412-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:50:35Z","timestamp":1559073035000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-012-9412-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,28]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9412"],"URL":"https:\/\/doi.org\/10.1007\/s00454-012-9412-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,28]]}}}