{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:26:47Z","timestamp":1778495207930,"version":"3.51.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1987,6,1]],"date-time":"1987-06-01T00:00:00Z","timestamp":549504000000},"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":[[1987,6]]},"DOI":"10.1007\/bf02187876","type":"journal-article","created":{"date-parts":[[2005,10,29]],"date-time":"2005-10-29T08:51:54Z","timestamp":1130575914000},"page":"127-151","source":"Crossref","is-referenced-by-count":455,"title":["\u025b-nets and simplex range queries"],"prefix":"10.1007","volume":"2","author":[{"given":"David","family":"Haussler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emo","family":"Welzl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1987,7,1]]},"reference":[{"key":"BF02187876_CR1","doi-asserted-by":"crossref","first-page":"233","DOI":"10.5802\/aif.938","volume":"33","author":"P. Assouad","year":"1983","unstructured":"P. Assouad, Densite et dimension,Ann. Inst. Fourier (Grenoble) 33 (1983), 233\u2013282.","journal-title":"Ann. Inst. Fourier (Grenoble)"},{"key":"BF02187876_CR2","doi-asserted-by":"crossref","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension,Proceedings of the 18th Symposium on Theory of Computation, 273\u2013282, 1986.","DOI":"10.1145\/12130.12158"},{"key":"BF02187876_CR3","doi-asserted-by":"crossref","unstructured":"B. Chazelle, L. Guibas, and D. T. Lee, The power of geometric duality,Proceedings of the 24th Symposium on Foundations of Computer Science, 217\u2013225, 1983.","DOI":"10.1109\/SFCS.1983.75"},{"key":"BF02187876_CR4","doi-asserted-by":"crossref","unstructured":"K. Clarkson, \u201cA probabilistic algorithm for the post office problem,\u201dProceedings of the 17th Symposium on Theory of Computation, 175\u2013185, 1985.","DOI":"10.1145\/22145.22165"},{"key":"BF02187876_CR5","doi-asserted-by":"crossref","unstructured":"K. Clarkson, Further applications of random sampling to computational geometry,Proceedings of the 18th Symposium on Theory of Computation, 414\u2013423, 1986.","DOI":"10.1145\/12130.12173"},{"key":"BF02187876_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BFb0015736","volume-title":"Partitioning point sets in 4 dimensions","author":"R. Cole","year":"1985","unstructured":"R. Cole, Partitioning point sets in 4 dimensions,Proceedings of the Colloquium on Automata, Language and Programming, 111\u2013119, Lecture Notes in Computer Science 194, Springer-Verlag, Berlin, 1985."},{"key":"BF02187876_CR7","unstructured":"D. Dobkin and H. Edelsbrunner, Organizing Points in Two and Three Dimensions, Technical Report F130, Technische Universitat Graz, 1984."},{"key":"BF02187876_CR8","unstructured":"D. Dobkin, H. Edelsbrunner, and F. Yao, A 3-space partition and its applications, manuscript."},{"key":"BF02187876_CR9","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1214\/aop\/1176995384","volume":"6","author":"R. M. Dudley","year":"1978","unstructured":"R. M. Dudley, Central limit theorems for empirical measures,Ann. Probab. 6 (1978), 899\u2013929.","journal-title":"Ann. Probab."},{"key":"BF02187876_CR10","first-page":"239","volume":"26","author":"H. Edelsbrunner","year":"1985","unstructured":"H. Edelsbrunner, Problem P110,Bull. EATCS 26 (1985), 239.","journal-title":"Bull. EATCS"},{"key":"BF02187876_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry, EATCS Monographs in Theoretical Computer Science","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner,Algorithms in Combinatorial Geometry, EATCS Monographs in Theoretical Computer Science, Springer-Verlag, Berlin, 1987."},{"key":"BF02187876_CR12","unstructured":"H. Edelsbrunner and F. Huber, Dissecting Sets of Points in Two and Three-Dimensions, Technical Report F138, Technische Universitat Graz, 1984."},{"key":"BF02187876_CR13","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1137\/0215019","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner and E. Welzl, Constructing belts in two-dimensional arrangements with applications,SIAM J. Comput. 15 (1986), 271\u2013284.","journal-title":"SIAM J. Comput."},{"key":"BF02187876_CR14","unstructured":"H. Edelsbrunner and E. Welzl, Halfplanar range search in linear space andO(n 0.695) query time,Inform. Process. Lett., to appear."},{"key":"BF02187876_CR15","volume-title":"Convex Polytopes","author":"Branko Gruenbaum","year":"1967","unstructured":"Branko Gruenbaum,Convex Polytopes, Interscience, New York, 1967."},{"key":"BF02187876_CR16","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N. Sauer","year":"1972","unstructured":"N. Sauer, On the density of families of sets,J. Combin. Theory Ser. A 13 (1972), 145\u2013147.","journal-title":"J. Combin. Theory Ser. A"},{"key":"BF02187876_CR17","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V. N. Vapnik","year":"1971","unstructured":"V. N. Vapnik and A. Ya. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities,Theory Probab. Appl. 16 (1971), 264\u2013280.","journal-title":"Theory Probab. Appl."},{"key":"BF02187876_CR18","volume-title":"The Theory of Pattern Recognition","author":"V. N. Vapnik","year":"1974","unstructured":"V. N. Vapnik and A. Ya. Chervonenkis,The Theory of Pattern Recognition, Nauka, Moscow, 1974."},{"key":"BF02187876_CR19","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0012-365X(81)90274-0","volume":"33","author":"R. S. Wenocur","year":"1981","unstructured":"R. S. Wenocur and R. M. Dudley, Some special Vapnik-Chervonenkis classes,Discrete Math. 33 (1981), 313\u2013318.","journal-title":"Discrete Math."},{"key":"BF02187876_CR20","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1137\/0211012","volume":"11","author":"D. Willard","year":"1982","unstructured":"D. Willard, Polygon retrieval,SIAM J. Comput. 11 (1982), 149\u2013165.","journal-title":"SIAM J. Comput."},{"key":"BF02187876_CR21","volume-title":"Convex Figures","author":"I. M. Yaglom","year":"1961","unstructured":"I. M. Yaglom and V. G. Bolyansky,Convex Figures, Holt, Rinehart and Winston, New York, 1961 (transl.)."},{"key":"BF02187876_CR22","doi-asserted-by":"crossref","unstructured":"F. Yao, A 3-space partition and it applications,Proceedings of the 15th Symposium on Theory of Computation, 258\u2013263, 1983.","DOI":"10.1145\/800061.808755"},{"key":"BF02187876_CR23","doi-asserted-by":"crossref","unstructured":"A. Yao and F. Yao, A general approach tod-dimensional geometric queries,Proceedings of the 17th Symposium on Theory of Computation, 163\u2013169, 1985.","DOI":"10.1145\/22145.22163"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187876.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02187876\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187876","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T15:21:54Z","timestamp":1586532114000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02187876"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,6]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1987,6]]}},"alternative-id":["BF02187876"],"URL":"https:\/\/doi.org\/10.1007\/bf02187876","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,6]]}}}