{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T03:19:30Z","timestamp":1774495170930,"version":"3.50.1"},"reference-count":30,"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\/bf02187879","type":"journal-article","created":{"date-parts":[[2005,10,29]],"date-time":"2005-10-29T08:51:54Z","timestamp":1130575914000},"page":"195-222","source":"Crossref","is-referenced-by-count":209,"title":["New applications of random sampling in computational geometry"],"prefix":"10.1007","volume":"2","author":[{"given":"Kenneth L.","family":"Clarkson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1987,6,1]]},"reference":[{"key":"BF02187879_CR1","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 Annual SIGACT Symposium, Berkeley, CA, 1986.","DOI":"10.1145\/12130.12158"},{"key":"BF02187879_CR2","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0020-0190(79)90074-7","volume":"9","author":"K. Q. Brown","year":"1979","unstructured":"K. Q. Brown, Voronoi diagrams from convex hull,Inform. Process. Lett. 9 (1979), 223\u2013228.","journal-title":"Inform. Process. Lett."},{"key":"BF02187879_CR3","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0019-9958(85)80045-0","volume":"64","author":"B. Chazelle","year":"1985","unstructured":"B. Chazelle, How to search in history,Inform. and Control 64 (1985), 77\u201399.","journal-title":"Inform. and Control"},{"key":"BF02187879_CR4","doi-asserted-by":"crossref","unstructured":"B. Chazelle and H. Edelsbrunner, An improved algorithm for constructingkth-order Voronoi diagrams,Proceedings of the First Symposium on Computational Geometry, 228\u2013234, Baltimore, MD, 1985.","DOI":"10.1145\/323233.323263"},{"key":"BF02187879_CR5","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02187685","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle and F. P. Preparata, Halfspace range search: an algorithmic application ofk-sets,Discrete Comput. Geom. 1 (1986), 83\u201394.","journal-title":"Discrete Comput. Geom."},{"key":"BF02187879_CR6","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, A probabilistic algorithm for the post office problem,Proceedings of the 17th Annual SIGACT Symposium, 75\u2013184, Providence, RI, 1985.","DOI":"10.1145\/22145.22165"},{"key":"BF02187879_CR7","series-title":"Technical Report","volume-title":"Partitioning Point Sets in Arbitrary Dimensions","author":"R. Cole","year":"1985","unstructured":"R. Cole, Partitioning Point Sets in Arbitrary Dimensions, Technical Report 184, Department of Computer Science, Courant Institute, New York, 1985."},{"key":"BF02187879_CR8","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/S0019-9958(84)80040-6","volume":"63","author":"R. Cole","year":"1984","unstructured":"R. Cole and C. K. Yap, Geometric retrieval problems,Inform. and Control 63 (1984), 112\u2013121.","journal-title":"Inform. and Control"},{"key":"BF02187879_CR9","doi-asserted-by":"crossref","unstructured":"R. Cole, M. Sharir, and C. Yap, Onk-hulls and related problems,Proceedings of the 16th Annual SIGACT Symposium, 154\u2013166, Washington, DC, 1984.","DOI":"10.1145\/800057.808677"},{"key":"BF02187879_CR10","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/0196-6774(85)90007-0","volume":"6","author":"D. P. Dobkin","year":"1985","unstructured":"D. P. Dobkin and D. G. Kirkpatrick, A linear algorithm for determining the separation of convex polyhedra,J. Algorithms 6 (1985), 381\u2013393.","journal-title":"J. Algorithms"},{"key":"BF02187879_CR11","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1137\/0205015","volume":"5","author":"D. Dobkin","year":"1976","unstructured":"D. Dobkin and R. J. Lipton, Multidimensional searching problems,SIAM J. Comput. 5 (1976), 181\u2013186.","journal-title":"SIAM J. Comput."},{"key":"BF02187879_CR12","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02187681","volume":"1","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner and R. Seidel, Voronoi diagrams and arrangements,Discrete Comput. Geom. 1 (1986), 25\u201344.","journal-title":"Discrete Comput. Geom."},{"key":"BF02187879_CR13","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0097-3165(85)90017-2","volume":"38","author":"H. Edelsbrunner","year":"1985","unstructured":"H. Edelsbrunner and E. Welzl, On the number of line separations of a finite set in the plane,J. Combin. Theory Ser. A 38 (1985), 15\u201329.","journal-title":"J. Combin. Theory Ser. A"},{"key":"BF02187879_CR14","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, J. O'Rourke, and R. Seidel, Constructing arrangements of lines and hyperplanes with applications,SIAM J. Comput. 15 (1986), 341\u2013363.","journal-title":"SIAM J. Comput."},{"key":"BF02187879_CR15","volume-title":"Probabilistic Methods in Combinatorics","author":"P. Erd\u00f6s","year":"1974","unstructured":"P. Erd\u00f6s and J. Spencer,Probabilistic Methods in Combinatorics, Academic Press, New York, 1974."},{"key":"BF02187879_CR16","volume-title":"A Survey of Combinatorial Theory","author":"P. Erd\u00f6s","year":"1973","unstructured":"P. Erd\u00f6s, L. Lovasz, A. Simmons, and E. G. Straus, Dissection graphs of planar point sets, inA Survey of Combinatorial Theory (J. N. Srivastavaet al., eds), North-Holland, Amsterdam 1973."},{"key":"BF02187879_CR17","volume-title":"Convex Polytopes","author":"B. Gr\u00fcnbaum","year":"1967","unstructured":"B. Gr\u00fcnbaum,Convex Polytopes, Wiley, New York, 1967."},{"key":"BF02187879_CR18","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"D. Haussler and E. Welzl,\u03b5-nets and simplex range queries,Discrete Comput. Geom. 2 (1987), 127\u2013151.","journal-title":"Discrete Comput. Geom."},{"key":"BF02187879_CR19","first-page":"13","volume":"5","author":"C. A. R. Hoare","year":"1962","unstructured":"C. A. R. Hoare, Quicksort,Comput. J. 5 (1962), 13\u201328.","journal-title":"Comput. J."},{"key":"BF02187879_CR20","volume-title":"The Art of Computer Programming, Vol. 3","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth,The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973."},{"key":"BF02187879_CR21","first-page":"478","volume":"31","author":"D. T. Lee","year":"1982","unstructured":"D. T. Lee, Onk-nearest neighbor Voronoi diagrams in the plane,IEEE Trans. Comput.,31 (1982), 478\u2013487.","journal-title":"IEEE Trans. Comput."},{"key":"BF02187879_CR22","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1112\/S0025579300002850","volume":"17","author":"P. McMullen","year":"1970","unstructured":"P. McMullen, The maximum number of faces of a convex polytope,Mathematika 17 (1970), 179\u2013184.","journal-title":"Mathematika"},{"key":"BF02187879_CR23","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":"F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985."},{"key":"BF02187879_CR24","doi-asserted-by":"crossref","unstructured":"R. Reischuk, A fast probabilistic parallel sorting algorithm,Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science, 212\u2013219, 1981.","DOI":"10.1109\/SFCS.1981.6"},{"key":"BF02187879_CR25","doi-asserted-by":"crossref","unstructured":"R. Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face,Proceedings of the 18th Annual SIGACT Symposium, Berkeley, CA, 1986.","DOI":"10.1145\/12130.12172"},{"key":"BF02187879_CR26","unstructured":"M. I. Shamos, Computational Geometry, Ph.D. thesis, Yale University, 1978."},{"key":"BF02187879_CR27","doi-asserted-by":"crossref","unstructured":"V. N. Vapnik and A. Y. A. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities,Theory Probab. Appl. 16 (1971).","DOI":"10.1137\/1116025"},{"key":"BF02187879_CR28","doi-asserted-by":"crossref","unstructured":"J. S. Vitter, Optimum algorithms for two random sampling problems,Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, 65\u201375, Tucson, AZ, 1983.","DOI":"10.1109\/SFCS.1983.43"},{"key":"BF02187879_CR29","doi-asserted-by":"crossref","unstructured":"D. Willard, Polygon retrieval,SIAM J. Comput. 11 (1982).","DOI":"10.1137\/0211012"},{"key":"BF02187879_CR30","doi-asserted-by":"crossref","unstructured":"A. C. Yao and F. F. Yao, A general approach tod-dimensional geometric queries,Proceedings of the 17th Annual SIGACT Symposium, 163\u2013168, Providence, RI, 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\/BF02187879.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02187879\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187879","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T15:21:58Z","timestamp":1586532118000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02187879"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,6]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1987,6]]}},"alternative-id":["BF02187879"],"URL":"https:\/\/doi.org\/10.1007\/bf02187879","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,6]]}}}