{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T10:38:41Z","timestamp":1648895921283},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,11,11]],"date-time":"2010-11-11T00:00:00Z","timestamp":1289433600000},"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":[[2011,1]]},"DOI":"10.1007\/s00454-010-9308-6","type":"journal-article","created":{"date-parts":[[2010,11,10]],"date-time":"2010-11-10T20:04:06Z","timestamp":1289419446000},"page":"3-33","source":"Crossref","is-referenced-by-count":5,"title":["Range Minima Queries with Respect to a Random Permutation, and Approximate Range Counting"],"prefix":"10.1007","volume":"45","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edgar","family":"Ramos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,11,11]]},"reference":[{"key":"9308_CR1","first-page":"337","volume-title":"Proc. 23rd Annu. ACM Sympos. Comput. Geom.","author":"P. Afshani","year":"2007","unstructured":"Afshani,\u00a0P., Chan, T.M.: On approximate range counting and depth. In: Proc. 23rd Annu. ACM Sympos. Comput. Geom., pp. 337\u2013343 (2007)"},{"issue":"4","key":"9308_CR2","doi-asserted-by":"crossref","first-page":"794","DOI":"10.1137\/0222051","volume":"22","author":"P.K. Agarwal","year":"1993","unstructured":"Agarwal, P.K., Matou\u0161ek,\u00a0J.: Ray shooting and parametric search. SIAM J. Comput. 22(4), 794\u2013806 (1993)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9308_CR3","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1137\/060669474","volume":"38","author":"B. Aronov","year":"2008","unstructured":"Aronov,\u00a0B., Har-Peled,\u00a0S.: On approximating the depth and related problems. SIAM J. Comput. 38(3), 899\u2013921 (2008)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"9308_CR4","doi-asserted-by":"crossref","first-page":"2704","DOI":"10.1137\/080736600","volume":"39","author":"B. Aronov","year":"2010","unstructured":"Aronov,\u00a0B., Sharir,\u00a0M.: Approximate range counting. SIAM J. Comput. 39(7), 2704\u20132725 (2010)","journal-title":"SIAM J. Comput."},{"key":"9308_CR5","first-page":"327","volume-title":"Proc. 23rd Annu. ACM Sympos. Comput. Geom.","author":"B. Aronov","year":"2007","unstructured":"Aronov,\u00a0B., Har-Peled,\u00a0S., Sharir,\u00a0M.: On approximate halfspace range counting and relative epsilon-approximations. In: Proc. 23rd Annu. ACM Sympos. Comput. Geom., pp. 327\u2013336 (2007)"},{"key":"9308_CR6","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, 561\u2013575 (2000)","journal-title":"SIAM J. Comput."},{"key":"9308_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511626371","volume-title":"The Discrepancy Method","author":"B. Chazelle","year":"2000","unstructured":"Chazelle,\u00a0B.: The Discrepancy Method. Cambridge University Press, Cambridge (2000)"},{"key":"9308_CR8","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. Clarkson","year":"1989","unstructured":"Clarkson,\u00a0K., Shor,\u00a0P.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9308_CR9","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0925-7721(93)90009-U","volume":"3","author":"K. Clarkson","year":"1993","unstructured":"Clarkson,\u00a0K., Mehlhorn,\u00a0K., Seidel,\u00a0R.: Four results on randomized incremental constructions. Comput. Geom. 3, 185\u2013212 (1993)","journal-title":"Comput. Geom."},{"key":"9308_CR10","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1006\/jcss.1997.1534","volume":"55","author":"E. Cohen","year":"1997","unstructured":"Cohen,\u00a0E.: Size-estimation framework with applications to transitive closure and reachability. J.\u00a0Comput. Syst. Sci. 55, 441\u2013453 (1997)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9308_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04245-8","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"2000","unstructured":"de Berg,\u00a0M., van Kreveld,\u00a0M., Overmars,\u00a0M., Schwarzkopf,\u00a0O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer, Heidelberg (2000)","edition":"2"},{"key":"9308_CR12","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1007\/BFb0032047","volume-title":"Proc. 17th Internat. Colloq. Automata, Languages and Programming","author":"D.P. Dobkin","year":"1990","unstructured":"Dobkin, D.P., Kirkpatrick, D.G.: Determining the separation of preprocessed polyhedra\u2014A\u00a0unified approach. In: Proc. 17th Internat. Colloq. Automata, Languages and Programming, pp. 400\u2013413 (1990)"},{"key":"9308_CR13","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,\u00a0H.: Algorithms in Combinatorial Geometry. Springer, Heidelberg (1987)"},{"key":"9308_CR14","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02187681","volume":"1","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner,\u00a0H., Seidel,\u00a0R.: Voronoi diagrams and arrangements. Discrete Comput. Geom. 1, 25\u201344 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"9308_CR15","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF01758770","volume":"7","author":"L. Guibas","year":"1992","unstructured":"Guibas,\u00a0L., Knuth, D.E., Sharir,\u00a0M.: Randomized incremental construction of Voronoi and Delaunay diagrams. Algorithmica 7, 381\u2013413 (1992)","journal-title":"Algorithmica"},{"key":"9308_CR16","unstructured":"Har-Peled,\u00a0S., Sharir,\u00a0M.: Relative \u03b5-approximations in geometry. Discrete Comput. Geom. in press. (Also in http:\/\/arxiv.org\/abs\/0909.0717 )"},{"key":"9308_CR17","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"Haussler,\u00a0D., Welzl,\u00a0E.: Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"9308_CR18","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1145\/1109557.1109611","volume-title":"Proc. 17th Annu. ACM-SIAM Sympos. Discrete Algo","author":"H. Kaplan","year":"2006","unstructured":"Kaplan,\u00a0H., Sharir,\u00a0M.: Randomized incremental constructions of three-dimensional convex hulls and planar Voronoi diagrams, and approximate range counting. In: Proc. 17th Annu. ACM-SIAM Sympos. Discrete Algo, pp. 484\u2013493 (2006)"},{"key":"9308_CR19","unstructured":"Kaplan,\u00a0H., Ramos,\u00a0E., Sharir,\u00a0M.: The overlay of minimization diagrams during a randomized incremental construction. Manuscript (2007)"},{"key":"9308_CR20","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1006\/jcss.2000.1741","volume":"62","author":"Y. Li","year":"2001","unstructured":"Li,\u00a0Y., Long, P.M., Srinivasan,\u00a0A.: Improved bounds on the sample complexity of learning. J.\u00a0Comput. Syst. Sci. 62, 516\u2013527 (2001)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9308_CR21","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,\u00a0J.: Reporting points in halfspaces. Comput. Geom. Theory Appl. 2, 169\u2013186 (1992)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9308_CR22","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J. Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek,\u00a0J.: Efficient partition trees. Discrete Comput. Geom. 8, 315\u2013334 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"9308_CR23","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek,\u00a0J.: Range searching with efficient hierarchical cuttings. Discrete Comput. Geom. 10, 157\u2013182 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9308_CR24","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF02573975","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek,\u00a0J., Schwarzkopf,\u00a0O.: On ray shooting in convex polytopes. Discrete Comput. Geom. 10, 215\u2013232 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9308_CR25","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1112\/S0025579300002850","volume":"17","author":"P. McMullen","year":"1970","unstructured":"McMullen,\u00a0P.: The maximum numbers of faces of a convex polytope. Mathematika 17, 179\u2013184 (1970)","journal-title":"Mathematika"},{"key":"9308_CR26","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1006\/inco.1993.1057","volume":"106","author":"S. Meiser","year":"1993","unstructured":"Meiser,\u00a0S.: Point location in arrangements of hyperplanes. Inf. Comput. 106, 286\u2013303 (1993)","journal-title":"Inf. Comput."},{"key":"9308_CR27","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K. Mulmuley","year":"1994","unstructured":"Mulmuley,\u00a0K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs (1994)"},{"key":"9308_CR28","first-page":"886","volume-title":"Proc. 8th Annu. ACM Sympos. Comput. Geom.","author":"O. Schwarzkopf","year":"1992","unstructured":"Schwarzkopf,\u00a0O.: Ray shooting in convex polytopes. In: Proc. 8th Annu. ACM Sympos. Comput. Geom., pp. 886\u2013894 (1992)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-010-9308-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-010-9308-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-010-9308-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T05:26:48Z","timestamp":1559798808000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-010-9308-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,11]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["9308"],"URL":"https:\/\/doi.org\/10.1007\/s00454-010-9308-6","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11,11]]}}}