{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T19:54:28Z","timestamp":1723146868973},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"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":[[1997,3]]},"DOI":"10.1007\/bf02523195","type":"journal-article","created":{"date-parts":[[2006,11,8]],"date-time":"2006-11-08T04:41:28Z","timestamp":1162960888000},"page":"322-329","source":"Crossref","is-referenced-by-count":16,"title":["Randomized quickhull"],"prefix":"10.1007","volume":"17","author":[{"given":"R.","family":"Wenger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"BF02523195_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., and Toussaint, G. T. A fast convex hull algorithm.Inform. Process. Lett. 7(5) (1978),219\u2013222.","journal-title":"Inform. Process. Lett."},{"key":"BF02523195_CR2","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/0020-0190(80)90125-8","volume":"11","author":"D. Avis","year":"1980","unstructured":"Avis, D. Comments on a lower bound for convex hull determination.Inform. Process. Lett. 11 (1980), 126.","journal-title":"Inform. Process. Lett."},{"key":"BF02523195_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 Shamos, M. I. Divide-and-conquer for linear expected time.Inform. Process. Lett. 7 (1978), 87\u201391.","journal-title":"Inform. Process. Lett."},{"key":"BF02523195_CR4","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/0020-0190(78)90021-2","volume":"7","author":"A. Bykat","year":"1978","unstructured":"Bykat, A. Convex hull of a finite set of points in two dimensions.Inform. Process. Lett. 7 (1978), 296\u2013298.","journal-title":"Inform. Process. Lett."},{"key":"BF02523195_CR5","doi-asserted-by":"crossref","unstructured":"Chan, T. Output-sensitive results on convex hulls, extreme points, and related problems.Proc. 11th Annu. ACM Symp. on Computational Geometry, 1995, pp. 10\u201319.","DOI":"10.1145\/220279.220281"},{"key":"BF02523195_CR6","unstructured":"Chan, T., Snoeyink, J., and Yap, C. K. Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three.Proc. 6th ACM-SIAM Symp. on Discrete Algorithms, 1995, pp. 282\u2013291."},{"key":"BF02523195_CR7","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. L. Clarkson","year":"1987","unstructured":"Clarkson, K. L. New applications of random sampling in computational geometry.Discrete Comput. Geom. 2 (1987), 195\u2013222.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523195_CR8","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"K. L. Clarkson","year":"1988","unstructured":"Clarkson, K. L. A randomized algorithm for closest-point queries.SIAM J. Comput. 17 (1988), 830\u2013847.","journal-title":"SIAM J. Comput."},{"key":"BF02523195_CR9","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. L. Clarkson","year":"1989","unstructured":"Clarkson, K. L., and Shor, P. W. Applications of random sampling in computational geometry, II.Discrete Comput. Geom. 4, (1989), 387\u2013421.","journal-title":"Discrete Comput. Geom."},{"key":"BF02523195_CR10","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0898-1221(81)90059-6","volume":"7","author":"L. P. Devroye","year":"1981","unstructured":"Devroye, L. P. How to reduce the average complexity of convex hull finding algorithms.Comput. Math. Appl. 7 (1981), 299\u2013308.","journal-title":"Comput. Math. Appl."},{"key":"BF02523195_CR11","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 Trans. Math. Software 3 (1977), 398\u2013403 and 411\u2013412.","journal-title":"ACM Trans. Math. Software"},{"key":"BF02523195_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 finite planar set.Inform. Process. Lett. 1 (1972), 132\u2013133.","journal-title":"Inform. Process. Lett."},{"key":"BF02523195_CR13","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1093\/comjnl\/22.3.262","volume":"22","author":"P. J. Green","year":"1979","unstructured":"Green, P. J., and Silverman, B. W. Constructing the convex hull of a set of points in the plane.Comput. J. 22 (1979), 262\u2013266.","journal-title":"Comput. J."},{"key":"BF02523195_CR14","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.Inform. Process. Lett. 2 (1973) 18\u201321.","journal-title":"Inform. Process. Lett."},{"key":"BF02523195_CR15","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"D. G. Kirkpatrick","year":"1986","unstructured":"Kirkpatrick, D. G., and Seidel, R. The ultimate planar convex hull algorithm?SIAM J. Comput. 15 (1986), 287\u2013299.","journal-title":"SIAM J. Comput."},{"key":"BF02523195_CR16","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0020-0190(78)90042-X","volume":"7","author":"J. Koplowitz","year":"1978","unstructured":"Koplowitz, J., and Jouppi, D. A more efficient convex hull algorithm.Inform. Process. Lett. 7 (1978), 56\u201357.","journal-title":"Inform. Process. Lett."},{"key":"BF02523195_CR17","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":"Preparata, F. P., and Shamos, M. I.Computational Geometry: an Introduction. Springer-Verlag, New York, 1985."},{"key":"BF02523195_CR18","doi-asserted-by":"crossref","unstructured":"Seidel, R. Backwards analysis of randomized geometric algorithms. InNew Trends in Discrete and Computational Geometry, J. Pach, Ed., Algorithms and Combinatorics, vol. 10. Springer-Verlag, 1993, pp. 37\u201368.","DOI":"10.1007\/978-3-642-58043-7_3"},{"key":"BF02523195_CR19","unstructured":"Shafer, L., and Steiger, W. Randomizing optimal geometric algorithms.Proc. 5th Canad. Conf. on Computational Geometry, Waterloo, 1993, pp. 133\u2013138."},{"key":"BF02523195_CR20","doi-asserted-by":"crossref","first-page":"780","DOI":"10.1145\/322276.322289","volume":"28","author":"A. C. Yao","year":"1981","unstructured":"Yao, A. C. A lower bound to finding convex hulls.J. Assoc. Comput. Mach. 28 (1981), 780\u2013787.","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523195.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02523195\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523195","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T20:39:41Z","timestamp":1558298381000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02523195"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["BF02523195"],"URL":"https:\/\/doi.org\/10.1007\/bf02523195","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}