{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T12:08:28Z","timestamp":1775650108255,"version":"3.50.1"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1981,12,1]],"date-time":"1981-12-01T00:00:00Z","timestamp":376012800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[1981,12]]},"DOI":"10.1007\/bf02237955","type":"journal-article","created":{"date-parts":[[2005,11,15]],"date-time":"2005-11-15T01:06:56Z","timestamp":1132016816000},"page":"361-366","source":"Crossref","is-referenced-by-count":40,"title":["A note on linear expected time algorithms for finding convex hulls","\u00dcber Algorithmen mit mittlerem linearen Zeitbedarf zur Bestimmung der konvexen H\u00fclle"],"prefix":"10.1007","volume":"26","author":[{"given":"L.","family":"Devroye","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G. T.","family":"Toussaint","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02237955_CR1","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0020-0190(78)90003-0","volume":"7","author":"S. G. Akl","year":"1978","unstructured":"Akl, S. G., Toussaint, G. T.: A fast convex hull algorithm. Information Processing Letters7, 219\u2013222 (1978).","journal-title":"Information Processing Letters"},{"key":"BF02237955_CR2","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., Shamos, M. I.: Divide and conquer for linear expected time. Information Processing Letters7, 87\u201391 (1978).","journal-title":"Information Processing Letters"},{"key":"BF02237955_CR3","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1145\/322092.322095","volume":"25","author":"J. L. Bentley","year":"1978","unstructured":"Bentley, J. L., Kung, H. T., Schkolnick, M., Thompson, C. D.: On the average number of maxima in a set of vectors and applications. Journal of the ACM25, 536\u2013543 (1978).","journal-title":"Journal of the ACM"},{"key":"BF02237955_CR4","doi-asserted-by":"crossref","unstructured":"Bentley, J. L., Weide, B. W., Yao, A. C.: Optimal expected-time algorithms for closest-point problems. Allerton Conference, Urbana, Illinois, 1978.","DOI":"10.21236\/ADA066740"},{"key":"BF02237955_CR5","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/BF00531885","volume":"15","author":"H. Carnal","year":"1970","unstructured":"Carnal, H.: Die konvexe H\u00fclle vonn rotationssymmetrisch verteilten Punkten. Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und verwandte. Gebiete15, 168\u2013176 (1970).","journal-title":"Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und verwandte. Gebiete"},{"key":"BF02237955_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02243418","volume":"26","author":"L. Devroye","year":"1980","unstructured":"Devroye, L., Klincsek, T.: Average time behavior of distributive sorting algorithms. Computing26, 1\u20137 (1980).","journal-title":"Computing"},{"key":"BF02237955_CR7","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 Letters11, 53\u201356 (1980a).","journal-title":"Information Processing Letters"},{"key":"BF02237955_CR8","doi-asserted-by":"crossref","unstructured":"Devroye, L.: How to reduce the average complexity of convex hull finding algorithms. Manuscript, McGill University, 1980 b.","DOI":"10.1016\/0898-1221(81)90059-6"},{"key":"BF02237955_CR9","doi-asserted-by":"crossref","first-page":"642","DOI":"10.1214\/aoms\/1177728174","volume":"27","author":"A. Dvoretzky","year":"1956","unstructured":"Dvoretzky, A., Kiefer, J., Wolfowitz, J.: Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Annals of Mathematical Statistics27, 642\u2013669 (1956).","journal-title":"Annals of Mathematical Statistics"},{"key":"BF02237955_CR10","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1145\/355759.355766","volume":"3","author":"W. F. Eddy","year":"1977","unstructured":"Eddy, W. F.: A new convex hull algorithm for planar sets. ACM Transactions on Mathematical Software3, 398\u2013403, 411\u2013412 (1977).","journal-title":"ACM Transactions on Mathematical Software"},{"key":"BF02237955_CR11","first-page":"148","volume":"2","author":"W. Feller","year":"1966","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications. Vol. 2, pp. 148. 1966.","journal-title":"An Introduction to Probability Theory and Its Applications"},{"key":"BF02237955_CR12","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 planar set. Information Processing Letters1, 132\u2013133 (1972).","journal-title":"Information Processing Letters"},{"key":"BF02237955_CR13","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0020-0190(73)90020-3","volume":"2","author":"R. A. Jarvis","year":"1973","unstructured":"Jarvis, R. A.: On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters2, 18\u201321 (1973).","journal-title":"Information Processing Letters"},{"key":"BF02237955_CR14","unstructured":"Shamos, M. I.: Computational geometry. Ph. D. thesis, Yale University, May 1978."}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02237955.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02237955\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02237955","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T11:53:05Z","timestamp":1683287585000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02237955"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,12]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1981,12]]}},"alternative-id":["BF02237955"],"URL":"https:\/\/doi.org\/10.1007\/bf02237955","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"value":"0010-485X","type":"print"},{"value":"1436-5057","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981,12]]}}}