{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:40:46Z","timestamp":1750308046439,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":18,"publisher":"ACM","license":[{"start":{"date-parts":[[2006,6,5]],"date-time":"2006-06-05T00:00:00Z","timestamp":1149465600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2006,6,5]]},"DOI":"10.1145\/1137856.1137860","type":"proceedings-article","created":{"date-parts":[[2006,7,24]],"date-time":"2006-07-24T16:53:01Z","timestamp":1153759981000},"page":"11-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["The effect of corners on the complexity of approximate range searching"],"prefix":"10.1145","author":[{"given":"Sunil","family":"Arya","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Theocharis","family":"Malamatos","sequence":"additional","affiliation":[{"name":"Stadtwald, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David M.","family":"Mount","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Maryland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,6,5]]},"reference":[{"key":"e_1_3_2_1_1_1","series-title":"Contemporary Mathematics","first-page":"1","volume-title":"Advances in Discrete and Computational Geometry","author":"Agarwal P. K.","year":"1999","unstructured":"P. K. Agarwal and J. Erickson . Geometric range searching and its relatives . In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry , volume 223 of Contemporary Mathematics , pages 1 -- 56 . American Mathematical Society , Providence, RI , 1999 . P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, volume 223 of Contemporary Mathematics, pages 1--56. American Mathematical Society, Providence, RI, 1999."},{"key":"e_1_3_2_1_2_1","first-page":"147","volume-title":"Proc. 13th Annu. ACM-SIAM Sympos. Discrete Algorithms","author":"Arya S.","year":"2002","unstructured":"S. Arya and T. Malamatos . Linear-size approximate Voronoi diagrams . In Proc. 13th Annu. ACM-SIAM Sympos. Discrete Algorithms pages 147 -- 155 , 2002 . S. Arya and T. Malamatos. Linear-size approximate Voronoi diagrams. In Proc. 13th Annu. ACM-SIAM Sympos. Discrete Algorithms pages 147--155, 2002."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510011"},{"key":"e_1_3_2_1_4_1","first-page":"535","volume-title":"Proc. 16th Annu. ACM-SIAM Sympos. Discrete Algorithms","author":"Arya S.","year":"2005","unstructured":"S. Arya , T. Malamatos , and D. M. Mount . Space-time tradeoffs for approximate spherical range counting . In Proc. 16th Annu. ACM-SIAM Sympos. Discrete Algorithms , pages 535 -- 544 , 2005 . S. Arya, T. Malamatos, and D. M. Mount. Space-time tradeoffs for approximate spherical range counting. In Proc. 16th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 535--544, 2005."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132598"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(00)00022-5"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01452053"},{"key":"e_1_3_2_1_8_1","volume-title":"Proc. III International Conference in Stochastic Geometry, Convex Bodies and Empirical Measures, Part II","volume":"65","author":"B\u00e1r\u00e1ny I.","year":"2000","unstructured":"I. B\u00e1r\u00e1ny . The technique of M-regions and cap-coverings: A survey . In Proc. III International Conference in Stochastic Geometry, Convex Bodies and Empirical Measures, Part II , volume 65 of Rendi. del Circ. Matemat. di Palermo, pages 21--38 , 2000 . I. B\u00e1r\u00e1ny. The technique of M-regions and cap-coverings: A survey. In Proc. III International Conference in Stochastic Geometry, Convex Bodies and Empirical Measures, Part II, volume 65 of Rendi. del Circ. Matemat. di Palermo, pages 21--38, 2000."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300015266"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573971"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1989-1001852-0"},{"key":"e_1_3_2_1_12_1","first-page":"154","volume-title":"Proc. 16th Canad. Conf. Comput. Geom.","author":"Chazelle B.","year":"2004","unstructured":"B. Chazelle , D. Liu , and A. Magen . Approximate range searching in higher dimension . In Proc. 16th Canad. Conf. Comput. Geom. , pages 154 -- 157 , 2004 . B. Chazelle, D. Liu, and A. Magen. Approximate range searching in higher dimension. In Proc. 16th Canad. Conf. Comput. Geom., pages 154--157, 2004."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798337212"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300002655"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210001"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573972"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/197405.197408"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214022"}],"event":{"name":"SoCG06: 22nd Annual Symposium on Computational Geometry","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Sedona Arizona USA","acronym":"SoCG06"},"container-title":["Proceedings of the twenty-second annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1137856.1137860","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1137856.1137860","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:14:30Z","timestamp":1750259670000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1137856.1137860"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6,5]]},"references-count":18,"alternative-id":["10.1145\/1137856.1137860","10.1145\/1137856"],"URL":"https:\/\/doi.org\/10.1145\/1137856.1137860","relation":{},"subject":[],"published":{"date-parts":[[2006,6,5]]},"assertion":[{"value":"2006-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}