{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T10:28:36Z","timestamp":1772447316926,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1991,9,1]],"date-time":"1991-09-01T00:00:00Z","timestamp":683683200000},"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":[[1991,9]]},"DOI":"10.1007\/bf02574694","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T10:31:20Z","timestamp":1174559480000},"page":"343-367","source":"Crossref","is-referenced-by-count":115,"title":["Higher-dimensional voronoi diagrams in linear expected time"],"prefix":"10.1007","volume":"6","author":[{"given":"Rex A.","family":"Dwyer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,6,26]]},"reference":[{"key":"BF02574694_CR1","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/BF01199118","volume":"55","author":"F. Affentranger","year":"1990","unstructured":"F. Affentranger, Random spheres in a convex body,Arch. der Math. 55 (1990), 74\u201381.","journal-title":"Arch. der Math."},{"key":"BF02574694_CR2","first-page":"159","volume-title":"Advances in Computing Research: Computational Geometry","author":"D. Avis","year":"1983","unstructured":"D. Avis and B. K. Bhattacharya, Algorithms for computingd-dimensional Voronoi diagrams and their duals, inAdvances in Computing Research: Computational Geometry, F. P. Preparata, ed., pp. 159\u2013180, JAI Press, Greenwich, CT, 1983."},{"key":"BF02574694_CR3","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1145\/355921.355927","volume":"6","author":"J. L. Bentley","year":"1980","unstructured":"J. L. Bentley, B. W. Weide, and A. C. Yao, Optimal expected-time algorithms for closest-point problems,ACM Trans. Math. Software 6 (1980), 563\u2013580.","journal-title":"ACM Trans. Math. Software"},{"key":"BF02574694_CR4","volume-title":"CRC Standard Mathematical Tables","author":"W. H. Beyer","year":"1984","unstructured":"W. H. Beyer,CRC Standard Mathematical Tables, 27th ed., CRC Press, Boca Raton, FL, 1984.","edition":"27th ed."},{"key":"BF02574694_CR5","unstructured":"B. Bhattacharya, Worst-case Analysis of a Convex Hull Algorithm, Technical Report, Simon Fraser University, 1982."},{"key":"BF02574694_CR6","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1093\/comjnl\/24.2.162","volume":"24","author":"A. Bowyer","year":"1981","unstructured":"A. Bowyer, Computing Dirichlet tessellations,Comput. J. 24 (1981), 162\u2013166.","journal-title":"Comput. J."},{"key":"BF02574694_CR7","volume-title":"Geometric Transforms for Fast Geometric Algorithms","author":"K. Q. Brown","year":"1979","unstructured":"K. Q. Brown, Geometric Transforms for Fast Geometric Algorithms, Ph.D. thesis, Carnegie-Mellon University, Pittsburgh, PA, 1979."},{"key":"BF02574694_CR8","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0021-9991(78)90110-9","volume":"29","author":"W. Browstow","year":"1978","unstructured":"W. Browstow, J.-P. Dussault, and B. L. Fox, Construction of Voronoi polyhedra,J. Comput. Phys. 29 (1978), 81\u201397.","journal-title":"J. Comput. Phys."},{"key":"BF02574694_CR9","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/321556.321564","volume":"17","author":"D. R. Chand","year":"1970","unstructured":"D. R. Chand and S. S. Kapur, An algorithm for convex polytopes,J. Assoc. Comput. Math. 17 (1970), 78\u201386.","journal-title":"J. Assoc. Comput. Math."},{"key":"BF02574694_CR10","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF01840356","volume":"2","author":"R. A. Dwyer","year":"1987","unstructured":"R. A. Dwyer, A faster divide-and-conquer algorithm for constructing Delaunay triangulations,Algorithmica 2 (1987), 137\u2013151.","journal-title":"Algorithmica"},{"key":"BF02574694_CR11","doi-asserted-by":"crossref","first-page":"688","DOI":"10.2307\/3214289","volume":"25","author":"R. A. Dwyer","year":"1988","unstructured":"R. A. Dwyer, On the convex hull of random points in a polytope,J. Appl. Probab. 25 (1988), 688\u2013699.","journal-title":"J. Appl. Probab."},{"key":"BF02574694_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":"BF02574694_CR13","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1093\/biomet\/52.3-4.331","volume":"52","author":"B. Efron","year":"1965","unstructured":"B. Efron, The convex hull of a random set of points,Biometrika 52 (1965), 331\u2013342.","journal-title":"Biometrika"},{"key":"BF02574694_CR14","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0021-9991(79)90146-3","volume":"32","author":"J. L. Finney","year":"1979","unstructured":"J. L. Finney, A procedure for the construction of Voronoi polyhedra,J. Comput. Phy. 32 (1979), 137\u2013143.","journal-title":"J. Comput. Phy."},{"key":"BF02574694_CR15","doi-asserted-by":"crossref","first-page":"958","DOI":"10.1214\/aoms\/1177704464","volume":"33","author":"E. N. Gilbert","year":"1962","unstructured":"E. N. Gilbert, Random subdivisions of space into crystals,Ann. Math. Statist. 33 (1962), 958\u2013972.","journal-title":"Ann. Math. Statist."},{"key":"BF02574694_CR16","volume-title":"A Course in the Geometry of n Dimensions","author":"M. G. Kendall","year":"1961","unstructured":"M. G. Kendall,A Course in the Geometry of n Dimensions, Hafner, New York, 1961."},{"key":"BF02574694_CR17","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF01937482","volume":"24","author":"A. Maus","year":"1984","unstructured":"A. Maus, Delaunay triangulation and the convex hull ofn points in expected linear time,BIT 24 (1984), 151\u2013163.","journal-title":"BIT"},{"key":"BF02574694_CR18","first-page":"270","volume":"8","author":"J. L. Meijering","year":"1953","unstructured":"J. L. Meijering, Interface area, edge length, and number of vertices in crystal aggregates with random nucleations,Philips Res. Rep. 8 (1953), 270\u2013290.","journal-title":"Philips Res. Rep."},{"key":"BF02574694_CR19","doi-asserted-by":"crossref","first-page":"353","DOI":"10.2307\/1426176","volume":"3","author":"R. E. Miles","year":"1971","unstructured":"R. E. Miles, Isotropic random simplices,Adv. Appl. Probab. 3 (1971), 353\u2013382.","journal-title":"Adv. Appl. Probab."},{"key":"BF02574694_CR20","first-page":"202","volume-title":"Stochastic Geometry","author":"R. E. Miles","year":"1974","unstructured":"R. E. Miles, A synopsis of \u201cPoisson flats in Euclidean spaces\u201d, inStochastic Geometry, E. F. Harding and D. G. Kendall, eds., pp. 202\u2013227, Wiley, New York, 1974."},{"key":"BF02574694_CR21","doi-asserted-by":"crossref","first-page":"35","DOI":"10.2307\/3212146","volume":"7","author":"H. Raynaud","year":"1970","unstructured":"H. Raynaud, Sur l'envelope convexe des nuages des points al\u00e9atoires dansR n , I,J. Appl. Probab 7 (1970), 35\u201348.","journal-title":"J. Appl. Probab"},{"key":"BF02574694_CR22","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF00535300","volume":"2","author":"A. R\u00e9nyi","year":"1963","unstructured":"A. R\u00e9nyi and R. Sulanke, \u00dcber die konvexe H\u00fclle vonn zuf\u00e4llig gew\u00e4hlten Punkten,Z. Wahrsch. Verw. Gebiete 2 (1963), 75\u201384.","journal-title":"Z. Wahrsch. Verw. Gebiete"},{"key":"BF02574694_CR23","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1007\/BF00535973","volume":"3","author":"A. R\u00e9nyi","year":"1964","unstructured":"A. R\u00e9nyi and R. Sulanke, \u00dcber die konvexe H\u00fclle vonn zuf\u00e4llig gew\u00e4hlten Punkten, II,Z. Wahrsch. Verw. Gebiete 3 (1964), 138\u2013147.","journal-title":"Z. Wahrsch. Verw. Gebiete"},{"key":"BF02574694_CR24","unstructured":"R. Seidel, The complexity of Voronoi diagrams in higher dimensions, inProc. 20th Ann. Allerton Conf. on Communication, Control, and Computing, pp. 94\u201395, University of Illinois at Urbana-Champaign, 1982."},{"key":"BF02574694_CR25","doi-asserted-by":"crossref","unstructured":"R. Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, inProc. 18th ACM Symp. on Theory of Computing, pp. 404\u2013413, ACM, 1986.","DOI":"10.1145\/12130.12172"},{"key":"BF02574694_CR26","doi-asserted-by":"crossref","unstructured":"R. Seidel, On the number of faces in higher-dimensional Voronoi diagrams, inProc. 3rd Ann. Symp. on Computational Geometry, pp. 181\u2013185, ACM, 1987.","DOI":"10.1145\/41958.41977"},{"key":"BF02574694_CR27","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0196-6774(85)90017-3","volume":"6","author":"G. Swart","year":"1985","unstructured":"G. Swart, Finding the convex hull facet by facet,J. Algorithms 6 (1985), 17\u201348.","journal-title":"J. Algorithms"},{"key":"BF02574694_CR28","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0021-9991(83)90087-6","volume":"51","author":"M. Tanemura","year":"1983","unstructured":"M. Tanemura, T. Ogawa, and N. Ogita, A new algorithm for three-dimensional Voronoi tessellation,J. Comput. Phys. 51 (1983), 191\u2013207.","journal-title":"J. Comput. Phys."},{"key":"BF02574694_CR29","series-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. E. Tarjan","year":"1983","unstructured":"R. E. Tarjan,Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, Vol. 44, Society of Industrial and Applied Mathematics, Philadelphia, PA, 1983."},{"key":"BF02574694_CR30","doi-asserted-by":"crossref","first-page":"1082","DOI":"10.1175\/1520-0493(1911)39<1248a:DNGB>2.0.CO;2","volume":"39","author":"A. H. Thiessen","year":"1911","unstructured":"A. H. Thiessen, Precipitation averages for large areas,Monthly Weather Rev. 39 (1911), 1082\u20131084.","journal-title":"Monthly Weather Rev."},{"key":"BF02574694_CR31","volume-title":"Funzioni Ipergeometriche Confluente","author":"F. G. Tricomi","year":"1954","unstructured":"F. G. Tricomi,Funzioni Ipergeometriche Confluente, Edizioni Cremonese, Rome, 1954."},{"key":"BF02574694_CR32","first-page":"198","volume":"134","author":"G. Voronoi","year":"1908","unstructured":"G. Voronoi, Nouvelles applications des parametres continus \u00e0 la theorie des formes quadratique, deuxi\u00e8me m\u00e9moire: recherches sur les parall\u00e9llo\u00e8dres primitifs,J. Reine Angew. Math. 134 (1908), 198\u2013287.","journal-title":"J. Reine Angew. Math."},{"key":"BF02574694_CR33","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1093\/comjnl\/24.2.167","volume":"24","author":"D. F. Watson","year":"1981","unstructured":"D. F. Watson, Computing then-dimensional Delaunay tessellation with application to Voronoi polytopes,Comput. J. 24 (1981), 167\u2013172.","journal-title":"Comput. J."},{"key":"BF02574694_CR34","volume-title":"A Course of Modern Analysis","author":"E. T. Whittaker","year":"1927","unstructured":"E. T. Whittaker and G. N. Watson,A Course of Modern Analysis, 4th edn., Cambridge University Press, Cambridge, 1927.","edition":"4th edn."},{"key":"BF02574694_CR35","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1103\/PhysRev.43.804","volume":"43","author":"E. Wigner","year":"1933","unstructured":"E. Wigner and F. Seitz, On the constitution of metallic sodium,Phy. Rev. 43, (1933), 804\u2013810.","journal-title":"Phy. Rev."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574694.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02574694\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T12:30:33Z","timestamp":1558182633000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02574694"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,9]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1991,9]]}},"alternative-id":["BF02574694"],"URL":"https:\/\/doi.org\/10.1007\/bf02574694","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,9]]}}}