{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,16]],"date-time":"2025-11-16T21:44:57Z","timestamp":1763329497199},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"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":[[1997,1]]},"DOI":"10.1007\/bf02770866","type":"journal-article","created":{"date-parts":[[2007,12,14]],"date-time":"2007-12-14T09:05:40Z","timestamp":1197623140000},"page":"79-109","source":"Crossref","is-referenced-by-count":9,"title":["Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points"],"prefix":"10.1007","volume":"17","author":[{"given":"K. H.","family":"Borgwardt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02770866_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.Information Processing Letters 7 (1978), 219\u2013222.","journal-title":"Information Processing Letters"},{"key":"BF02770866_CR2","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF02293050","volume":"8","author":"D. Avis","year":"1992","unstructured":"Avis, D., and Fukuda, K. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra.Discrete & Computational Geometry 8 (1992), 295\u2013313.","journal-title":"Discrete & Computational Geometry"},{"issue":"2","key":"BF02770866_CR3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0020-0190(78)90051-0","volume":"7","author":"J. Bentley","year":"1978","unstructured":"Bentley, J., and Shamos, M. Divide and conquer for linear expected time.Information Processing Letters 7(2) (1978), 87\u201391.","journal-title":"Information Processing Letters"},{"key":"BF02770866_CR4","volume-title":"Algorithms and Combinatorics","author":"K. H. Borgwardt","year":"1987","unstructured":"Borgwardt, K. H. The Simplex method. A probabilistic analysis. InAlgorithms and Combinatorics, Vol. 1, Graham, R. L., Korte, B., and Lov\u00e1sz, L., eds., Springer-Verlag, Berlin, 1987."},{"key":"BF02770866_CR5","doi-asserted-by":"crossref","unstructured":"Borgwardt, K. H., Gaffke, N., J\u00fcnger, M., and Reinelt, G. Computing the convex hull in the Euclidean plane in linear expected time. InApplied Geometry and Discrete Mathematics (The Victor Klee Festschrift), Vol. 4, Gritzmann, P., and Sturmfels, B., eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1991, pp. 91\u2013107.","DOI":"10.1090\/dimacs\/004\/07"},{"key":"BF02770866_CR6","first-page":"1","volume-title":"Zahlentheoretische Analysis, Lecture Notes in Mathematics","author":"C. Buchta","year":"1985","unstructured":"Buchta, C. Zuf\u00c4llige Polyeder\u2014eine \u00fcbersicht. InZahlentheoretische Analysis, Lecture Notes in Mathematics, Vol. 1114, Hlawka, E., ed., Springer-Verlag, Berlin, 1985, pp. 1\u201313."},{"issue":"1","key":"BF02770866_CR7","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/321556.321564","volume":"17","author":"D. R. Chand","year":"1970","unstructured":"Chand, D. R., and Kapur, S. S. An algorithm for convex polytopes.Journal of the Associationfor Computing Machinery 17(1) (1970), 78\u201386.","journal-title":"Journal of the Associationfor Computing Machinery"},{"issue":"1","key":"BF02770866_CR8","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0020-0190(86)90037-2","volume":"22","author":"K. L. Clarkson","year":"1986","unstructured":"Clarkson, K. L. Linear programming inO(n3 dxd ) time.Information Processing Letters 22(1) (1986), 21\u201324.","journal-title":"Information Processing Letters"},{"key":"BF02770866_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 & Computational Geometry 4 (1989), 387\u2013421.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02770866_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.Computers and Mathematics with Applications 7 (1981), 299\u2013308.","journal-title":"Computers and Mathematics with Applications"},{"key":"BF02770866_CR11","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02280782","volume":"30","author":"L. P. Devroye","year":"1983","unstructured":"Devroye, L. P. Moment inequalities for random variables in computational geometry.Computing 30 (1983), 111\u2013119.","journal-title":"Computing"},{"key":"BF02770866_CR12","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF02237955","volume":"26","author":"L. P. Devroye","year":"1981","unstructured":"Devroye, L. P., and Toussaint, G. T. A note on linear expected time algorithms for finding convex hulls.Computing 26 (1981), 361\u2013366.","journal-title":"Computing"},{"key":"BF02770866_CR13","unstructured":"Dwyer, R. A. Average-Case Analysis of Algorithms for Convex Hulls and Voronoi Diagrams. CMU-CS88-132, Computer Science Dept., Carnegie-Mellon University, 1988."},{"key":"BF02770866_CR14","doi-asserted-by":"crossref","first-page":"688","DOI":"10.2307\/3214289","volume":"25","author":"R. A. Dwyer","year":"1988","unstructured":"Dwyer, R. A. On the convex hull of random points in a polytope.Journal of Applied Probability 25 (1988), 688\u2013699.","journal-title":"Journal of Applied Probability"},{"key":"BF02770866_CR15","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/BF01198169","volume":"86","author":"R. A. Dwyer","year":"1990","unstructured":"Dwyer, R. A. Random convex hulls in a product of balls.Probability Theory and Related Fields 86 (1990), 457\u201367.","journal-title":"Probability Theory and Related Fields"},{"key":"BF02770866_CR16","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0166-218X(91)90064-4","volume":"31","author":"R. A. Dwyer","year":"1991","unstructured":"Dwyer, R. A. Convex hulls of samples from spherically symmetric distributions.Discrete Applied Mathematics 31 (1991), 113\u2013132.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"BF02770866_CR17","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1137\/0213003","volume":"13","author":"M. E. Dyer","year":"1984","unstructured":"Dyer, M. E. Linear time algorithms for twoand three-variable linear programs.SIAM Journal of Computing 13(1) (1984), 31\u20135.","journal-title":"SIAM Journal of Computing"},{"key":"BF02770866_CR18","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF01587088","volume":"44","author":"M. E. Dyer","year":"1989","unstructured":"Dyer, M. E., and Frieze, A. M. A randomized algorithm for fixed-dimensional linear programming.Mathematical Programming 44 (1989), 203\u2013212.","journal-title":"Mathematical Programming"},{"key":"BF02770866_CR19","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.Information Processing Letters 1 (1972), 132\u2013133.","journal-title":"Information Processing Letters"},{"key":"BF02770866_CR20","unstructured":"J\u00fcnger, M., and Reinelt, G. Fast Computation of Convex Hulls. Schwerpunktprogramm der DFG: Anwendungsbezogene Optimierung und Steuerung, No. 137, Universit\u00c4t Augsburg, 1989."},{"key":"BF02770866_CR21","unstructured":"Kallay, M. Convex Hull Algorithms in Higher Dimensions. Dept. Mathematics, University of Oklahoma, 1981."},{"key":"BF02770866_CR22","unstructured":"K\u00fcfer, K. Asymptotische Varianzanalysen in der stochastischen Polyedertheorie. Doktorarbeit, Universit\u00c4t Kaiserslautern, 1992."},{"key":"BF02770866_CR23","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"Megiddo, N. Linear programming in linear time when the dimension is fixed.Journal of the Association for Computing Machinery 31 (1984), 114\u2013127.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF02770866_CR24","unstructured":"Seidel, R. A Convex Hull Algorithm Optimal for Points in Even Dimensions. Master\u2019s thesis. University of British Columbia, 1981."},{"key":"BF02770866_CR25","doi-asserted-by":"crossref","unstructured":"Seidel, R. Constructing higher dimensional convex hulls at logarithmic cost per face.Proceedings of the 18thAnnual SIGACT Symposium, 1986, pp. 404\u2013413.","DOI":"10.1145\/12130.12172"},{"key":"BF02770866_CR26","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BF02574699","volume":"6","author":"R. Seidel","year":"1991","unstructured":"Seidel, R. Small-dimensional linear programming and convex hulls made easy.Discrete & Computational Geometry 6 (1991), 423\u201334.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02770866_CR27","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0196-6774(85)90017-3","volume":"6","author":"G. Swart","year":"1985","unstructured":"Swart, G. Finding the convex hull facet by facet.Journal of Algorithms 6 (1985), 17\u201348.","journal-title":"Journal of Algorithms"},{"key":"BF02770866_CR28","doi-asserted-by":"crossref","first-page":"259","DOI":"10.2307\/3214033","volume":"26","author":"B. F. Van Wel","year":"1989","unstructured":"Van Wel, B. F. The convex hull of a uniform sample from the interior of a simple d-polytope.Journal of Applied Probability 26 (1989), 259\u2013273.","journal-title":"Journal of Applied Probability"},{"key":"BF02770866_CR29","doi-asserted-by":"crossref","first-page":"109","DOI":"10.7146\/math.scand.a-10655","volume":"11","author":"J. G. Wendel","year":"1962","unstructured":"Wendel, J. G. A problem in geometric probability.Mathematica Scandinavica 11 (1962), 109\u2013111.","journal-title":"Mathematica Scandinavica"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02770866.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02770866\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02770866","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T02:02:36Z","timestamp":1558404156000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02770866"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["BF02770866"],"URL":"https:\/\/doi.org\/10.1007\/bf02770866","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}