{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:15:43Z","timestamp":1779174943484,"version":"3.51.4"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1993,2,1]],"date-time":"1993-02-01T00:00:00Z","timestamp":728524800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1993,2]]},"DOI":"10.1007\/bf01188711","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T22:39:58Z","timestamp":1108679998000},"page":"168-183","source":"Crossref","is-referenced-by-count":39,"title":["Fast linear expected-time algorithms for computing maxima and convex hulls"],"prefix":"10.1007","volume":"9","author":[{"given":"Jon L.","family":"Bentley","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenneth L.","family":"Clarkson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David B.","family":"Levine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"CR1","first-page":"169","volume":"41","author":"R. A. Becker","year":"1987","unstructured":"Becker, R. A., L. Denby, R. McGill, and A. R. Wilks, Analysis of data from the Places Rated Almanac,The American Statistician,41(3) (1987), 169?186.","journal-title":"The American Statistician"},{"issue":"4","key":"CR2","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/358841.358850","volume":"23","author":"J. L. Bentley","year":"1980","unstructured":"Bentley, J. L., Multidimensional divide-and-conquer,Communications of the Association for Computing Machinery,23(4) (1980), 214?229.","journal-title":"Communications of the Association for Computing Machinery"},{"issue":"2","key":"CR3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0020-0190(78)90051-0","volume":"7","author":"J. L. Bentley","year":"1978","unstructured":"Bentley, J. L., and M. I. Shamos, Divide and conquer for linear expected time,Information Processing Letters,7(2) (1978), 87?91.","journal-title":"Information Processing Letters"},{"issue":"4","key":"CR4","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1145\/322092.322095","volume":"25","author":"J. L. Bentley","year":"1978","unstructured":"Bentley. J. L., H. T. Kung, M. Schkolnick, and C. D. Thompson, On the average number of maxima in a set of vectors and applications,Journal of the Association for Computing Machinery,25(4) (1978), 536?543.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"4","key":"CR5","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1145\/355921.355927","volume":"6","author":"J. L. Bentley","year":"1986","unstructured":"Bentley, J. L., B. W., Weide, and A. C. Yao, Optimal exptected-time algorithms for closest point problems,ACM Transactions on Mathematical Software,6(4) (1986), 563?580.","journal-title":"ACM Transactions on Mathematical Software"},{"key":"CR6","unstructured":"Boyer, R., and D. Savageau,Places Related Almanac (Revised Edition), Rand McNally, 1985."},{"issue":"5","key":"CR7","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. L. Clarkson","year":"1989","unstructured":"Clarkson, K. L., and P. W. Shor, Applications of random sampling in computational geometry, II,Discrete and Computational Geometry,4(5) (1989), 387?421.","journal-title":"Discrete and Computational Geometry"},{"issue":"1","key":"CR8","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0020-0190(80)90036-8","volume":"11","author":"L. Devroye","year":"1980","unstructured":"Devroye, L.. A note on finding convex hulls via maximal vectors,Information Processing Letters,11(1) (1980), 53?56.","journal-title":"Information Processing Letters"},{"issue":"9","key":"CR9","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1145\/360680.360691","volume":"18","author":"R. W. Floyd","year":"1975","unstructured":"Floyd, R. W., and R. L. Rivest, Expected time bounds for selection,Communications of the ACM,18(9) (1975), 165?172.","journal-title":"Communications of the ACM"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"Golin, M., and R. Sedgewick, Analysis of a simple yet efficient convex hull algorithm,Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988, pp. 153?163.","DOI":"10.1145\/73393.73409"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. L. Graham","year":"1972","unstructured":"Graham, R. L., An efficient algorithm for determining the convex hull of a finite planar point set,Information Processing Letters,1 (1972), 132?133.","journal-title":"Information Processing Letters"},{"issue":"4","key":"CR12","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/321906.321910","volume":"22","author":"H. T. Kung","year":"1975","unstructured":"Kung, H. T., F. Luccio, and F. P. Preparata, On finding the maxima of a set of vectors,Journal of the Association for Computing Machinery,22(4) (1975), 469?476.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"1","key":"CR13","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/0196-6774(80)90005-X","volume":"1","author":"L. Monier","year":"1980","unstructured":"Monier, L., Combinatorial solutions of multidimensional divide-and-conquer recurrences,Journal of Algorithms,1(1) (1980), 60?74.","journal-title":"Journal of Algorithms"},{"issue":"2","key":"CR14","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1145\/359423.359430","volume":"20","author":"F. P. Preparata","year":"1977","unstructured":"Preparata, F. P., and S. J. Hong, Convex hulls of finite sets of points in two and three dimensions,Communications of the Association for Computing Machinery,20(2) (1977), 87?93.","journal-title":"Communications of the Association for Computing Machinery"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"Preparata, F. P., and M. I. Shamos,Computational Geometry, Springer-Verlag, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"CR16","series-title":"Technical Report","volume-title":"M.Sc. Thesis","author":"R. Seidel","year":"1981","unstructured":"Seidel, R., A convex hull algorithm optimal for points in even dimensions, M.Sc. Thesis, Technical Report 81-14, Department of Computer Science, University of British Columbia, Vancouver, 1981."},{"key":"CR17","unstructured":"Urgel, J., Private communication, Harvard Business School, April?May 1989."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188711.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01188711\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188711","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T16:41:47Z","timestamp":1556728907000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01188711"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,2]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,2]]}},"alternative-id":["BF01188711"],"URL":"https:\/\/doi.org\/10.1007\/bf01188711","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,2]]}}}