{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T02:18:35Z","timestamp":1672625915873},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,4,30]],"date-time":"2009-04-30T00:00:00Z","timestamp":1241049600000},"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":[[2009,7]]},"DOI":"10.1007\/s00454-009-9177-z","type":"journal-article","created":{"date-parts":[[2009,5,4]],"date-time":"2009-05-04T18:18:41Z","timestamp":1241461121000},"page":"3-21","source":"Crossref","is-referenced-by-count":14,"title":["On Approximate Range Counting and Depth"],"prefix":"10.1007","volume":"42","author":[{"given":"Peyman","family":"Afshani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timothy M.","family":"Chan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,4,30]]},"reference":[{"key":"9177_CR1","doi-asserted-by":"crossref","unstructured":"Afshani, P., Chan, T.M.: Optimal halfspace range reporting in three dimensions. In: Proceedings of the 20th Annual Symposium on Discrete Algorithms, pp. 180\u2013186 (2009)","DOI":"10.1137\/1.9781611973068.21"},{"key":"9177_CR2","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":"9177_CR3","unstructured":"Aronov, B., Har-Peled, S.: On approximating the depth and related problems. In: Proceedings of the 16th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 886\u2013894 (2005). Updated version at http:\/\/valis.cs.uiuc.edu\/~sariel\/research\/papers\/04\/depth\/ , downloaded in November 2006"},{"issue":"3-4","key":"9177_CR4","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0925-7721(00)00022-5","volume":"17","author":"S. Arya","year":"2000","unstructured":"Arya, S., Mount, D.M.: Approximate range searching. Comput. Geom. Theory Appl. 17(3-4), 135\u2013152 (2000)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9177_CR5","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1142\/S0218195995000210","volume":"5","author":"M. Berg de","year":"1995","unstructured":"de Berg, M., Schwarzkopf, O.: Cuttings and applications. Int. J. Comput. Geom. Appl. 5, 343\u2013355 (1995)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9177_CR6","doi-asserted-by":"crossref","unstructured":"Bern, M., Eppstein, D.: Multivariate regression depth. In: Proceedings of the 16th Annual Symposium on Computational Geometry, pp. 315\u2013321 (2000)","DOI":"10.1145\/336154.336218"},{"key":"9177_CR7","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: Fixed-dimensional linear programming queries made easy. In: Proceedings of the 12th Annual ACM Symposium on Computational Geometry, pp. 284\u2013290 (1996)","DOI":"10.1145\/237218.237397"},{"key":"9177_CR8","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF02712874","volume":"16","author":"T.M. Chan","year":"1996","unstructured":"Chan, T.M.: Output-sensitive results on convex hulls, extreme points, and related problems. Discrete Comput. Geom. 16, 369\u2013387 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"9177_CR9","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1007\/PL00009478","volume":"22","author":"T.M. Chan","year":"1999","unstructured":"Chan, T.M.: Geometric applications of a randomized optimization technique. Discrete Comput. Geom. 22, 547\u2013567 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"9177_CR10","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1137\/S0097539703439404","volume":"34","author":"T.M. Chan","year":"2000","unstructured":"Chan, T.M.: Low-dimensional linear programming with violations. SIAM J. Comput. 34, 879\u2013893 (2000)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9177_CR11","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1137\/S0097539798349188","volume":"30","author":"T.M. Chan","year":"2000","unstructured":"Chan, T.M.: Random sampling, halfspace range reporting, and construction of (\u2264k)-levels in three dimensions. SIAM J. Comput. 30(2), 561\u2013575 (2000)","journal-title":"SIAM J. Comput."},{"key":"9177_CR12","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1142\/S0218195901000511","volume":"11","author":"T.M. Chan","year":"2001","unstructured":"Chan, T.M.: On enumerating and selecting distances. Int. J. Comput. Geom. Appl. 11, 291\u2013304 (2001)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9177_CR13","unstructured":"Chan, T.M.: An optimal randomized algorithm for maximum Tukey depth. In: Proceedings of the 15th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 430\u2013436 (2004)"},{"issue":"1","key":"9177_CR14","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/BF01934990","volume":"25","author":"B. Chazelle","year":"1985","unstructured":"Chazelle, B., Guibas, L.J., Lee, D.T.: The power of geometric duality. BIT 25(1), 76\u201390 (1985)","journal-title":"BIT"},{"key":"9177_CR15","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K.L. Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry,\u00a0II. Discrete Comput. Geom. 4, 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9177_CR16","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1006\/jcss.1997.1534","volume":"55","author":"E. Cohen","year":"1997","unstructured":"Cohen, E.: Size-estimation framework with applications to transitive closure and reachability. J. Comput. Syst. Sci. 55, 441\u2013453 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9177_CR17","series-title":"EATCS Monographs on Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, vol.\u00a010. Springer, Heidelberg (1987)"},{"key":"9177_CR18","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1137\/0215019","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Welzl, E.: Constructing belts in two-dimensional arrangements with applications. SIAM J. Comput. 15, 271\u2013284 (1986)","journal-title":"SIAM J. Comput."},{"key":"9177_CR19","unstructured":"Har-Peled, S., Sharir, M.: Relative \u03b5-approximations in geometry. http:\/\/valis.cs.uiuc.edu\/~sariel\/research\/papers\/06\/relative\/ (2006). Also with B. Aronov, in Proceedings of the 23rd ACM Symposium on Computational Geometry, pp. 327\u2013336 (2007)"},{"issue":"2","key":"9177_CR20","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579170","volume":"6","author":"S. Hart","year":"1986","unstructured":"Hart, S., Sharir, M.: Nonlinearity of Davenport\u2013Schinzel sequences and of generalized path compression schemes. Combinatorica 6(2), 151\u2013177 (1986)","journal-title":"Combinatorica"},{"key":"9177_CR21","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."},{"key":"9177_CR22","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Sharir, M.: Randomized incremental constructions of three-dimensional convex hulls and planar Voronoi diagrams, and approximate range counting. In: Proceedings of the 17th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 484\u2013493 (2006)","DOI":"10.1145\/1109557.1109611"},{"key":"9177_CR23","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Ramos, E., Sharir, M.: Range minima queries with respect to a random permutation, and approximate range counting. Discrete Comput. Geom. (to appear)","DOI":"10.1007\/s00454-010-9308-6"},{"key":"9177_CR24","unstructured":"Kaplan, H., Ramos, E., Sharir, M.: The overlay of minimization diagrams in a randomized incremental construction. Manuscript (2007)"},{"issue":"2","key":"9177_CR25","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/s00454-003-0011-x","volume":"30","author":"S. Langerman","year":"2003","unstructured":"Langerman, S., Steiger, W.: The complexity of hyperplane depth in the plane. Discrete Comput. Geom. 30(2), 299\u2013309 (2003)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"9177_CR26","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J. Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Reporting points in halfspaces. Comput. Geom. Theory Appl. 2(3), 169\u2013186 (1992)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"2","key":"9177_CR27","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":"9177_CR28","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02570713","volume":"14","author":"J. Matou\u0161ek","year":"1995","unstructured":"Matou\u0161ek, J.: On geometric optimization with few violated constraints. Discrete Comput. Geom. 14, 365\u2013384 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"9177_CR29","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"key":"9177_CR30","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K. Mulmuley","year":"1994","unstructured":"Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs (1994)"},{"key":"9177_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)"},{"key":"9177_CR32","doi-asserted-by":"crossref","unstructured":"Ramos, E.A.: On range reporting, ray shooting and k-level construction. In: Proceedings of the 14th Annual Symposium on Computational Geometry, pp. 390\u2013399 (1999)","DOI":"10.1145\/304893.304993"},{"issue":"446","key":"9177_CR33","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1080\/01621459.1999.10474129","volume":"94","author":"P.J. Rousseeuw","year":"1999","unstructured":"Rousseeuw, P.J., Hubert, M.: Regression depth. J. Am. Stat. Assoc. 94(446), 388\u2013402 (1999)","journal-title":"J. Am. Stat. Assoc."},{"key":"9177_CR34","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s00454-001-0005-3","volume":"26","author":"M. Sharir","year":"2001","unstructured":"Sharir, M., Smorodinsky, S., Tardos, G.: An improved bound for k-sets in three dimensions. Discrete Comput. Geom. 26, 195\u2013204 (2001)","journal-title":"Discrete Comput. Geom."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9177-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-009-9177-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9177-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:47:37Z","timestamp":1559087257000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-009-9177-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,30]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,7]]}},"alternative-id":["9177"],"URL":"https:\/\/doi.org\/10.1007\/s00454-009-9177-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4,30]]}}}