{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:09:28Z","timestamp":1763467768443},"reference-count":39,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2007,2,1]],"date-time":"2007-02-01T00:00:00Z","timestamp":1170288000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":2358,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Geometry"],"published-print":{"date-parts":[[2007,2]]},"DOI":"10.1016\/j.comgeo.2006.05.005","type":"journal-article","created":{"date-parts":[[2006,11,2]],"date-time":"2006-11-02T18:32:19Z","timestamp":1162492339000},"page":"89-105","source":"Crossref","is-referenced-by-count":15,"title":["On the stabbing number of a random Delaunay triangulation"],"prefix":"10.1016","volume":"36","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[]},{"given":"Luc","family":"Devroye","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.comgeo.2006.05.005_bib001","series-title":"Handbook of Discrete and Computational Geometry","first-page":"575","article-title":"Range searching","author":"Agarwal","year":"1997"},{"key":"10.1016\/j.comgeo.2006.05.005_bib002","series-title":"The Probabilistic Method","author":"Alon","year":"1992"},{"key":"10.1016\/j.comgeo.2006.05.005_bib003","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","article-title":"Fast probabilistic algorithms for Hamiltonian circuits and matchings","volume":"18","author":"Angluin","year":"1979","journal-title":"Journal of Computer and System Sciences"},{"key":"10.1016\/j.comgeo.2006.05.005_bib004","doi-asserted-by":"crossref","first-page":"357","DOI":"10.2748\/tmj\/1178243286","article-title":"Weighted sums of certain dependent random variables","volume":"37","author":"Azuma","year":"1967","journal-title":"Tohoku Mathematical Journal"},{"key":"10.1016\/j.comgeo.2006.05.005_bib005","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1145\/355921.355927","article-title":"Optimal expected-time algorithms for closest point problems","volume":"6","author":"Bentley","year":"1980","journal-title":"ACM Transactions on Mathematical Software"},{"key":"10.1016\/j.comgeo.2006.05.005_bib006","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1142\/S0218195991000074","article-title":"The expected extremes in a Delaunay triangulation","volume":"1","author":"Bern","year":"1991","journal-title":"International Journal of Computational Geometry and Its Applications"},{"key":"10.1016\/j.comgeo.2006.05.005_bib007","series-title":"Triangulation de Delaunay et Maillages","author":"Borouchaki","year":"1997"},{"key":"10.1016\/j.comgeo.2006.05.005_bib008","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/S0925-7721(98)00004-2","article-title":"Intersections with random geometric objects","volume":"10","author":"Bose","year":"1998","journal-title":"Computational Geometry: Theory and Applications"},{"key":"10.1016\/j.comgeo.2006.05.005_bib009","doi-asserted-by":"crossref","unstructured":"P. Bose, P. Morin, Online routing in triangulations, in: International Symposium on Algorithms and Computation, 1999, pp. 113\u2013122","DOI":"10.1007\/3-540-46632-0_12"},{"key":"10.1016\/j.comgeo.2006.05.005_bib010","article-title":"On the Size of a Random Sphere of Influence Graph","volume":"vol. 31","author":"Chalker","year":"1999"},{"key":"10.1016\/j.comgeo.2006.05.005_bib011","series-title":"Introduction to Algorithms","author":"Cormen","year":"1990"},{"key":"10.1016\/j.comgeo.2006.05.005_bib012","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.comgeo.2004.02.002","article-title":"Expected time analysis for Delaunay point location","volume":"29","author":"Devroye","year":"2004","journal-title":"Computational Geometry Theory and Applications"},{"key":"10.1016\/j.comgeo.2006.05.005_bib013","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/BF02187801","article-title":"Delaunay graphs are almost as good as complete graphs","volume":"5","author":"Dobkin","year":"1990","journal-title":"Discrete Computational Geometry"},{"key":"10.1016\/j.comgeo.2006.05.005_bib014","unstructured":"J. Gilbert, Graph separator theorems and sparse Gaussian elimination, PhD dissertation, Stanford University, 1980"},{"key":"10.1016\/j.comgeo.2006.05.005_bib015","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/BF01396660","article-title":"The analysis of a nested dissection algorithm","volume":"50","author":"Gilbert","year":"1987","journal-title":"Numerische Mathematik"},{"key":"10.1016\/j.comgeo.2006.05.005_bib016","series-title":"Microsurveys in Discrete Probability","first-page":"43","article-title":"Beyond the method of bounded differences","volume":"vol. 41","author":"Godbole","year":"1998"},{"key":"10.1016\/j.comgeo.2006.05.005_bib017","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1093\/comjnl\/21.2.168","article-title":"Computing Dirichlet tessellations in the plane","volume":"21","author":"Green","year":"1978","journal-title":"The Computer Journal"},{"key":"10.1016\/j.comgeo.2006.05.005_bib018","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/282918.282923","article-title":"Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams","volume":"4","author":"Guibas","year":"1985","journal-title":"ACM Transactions on Graphics"},{"key":"10.1016\/j.comgeo.2006.05.005_bib019","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding","year":"1963","journal-title":"Journal of the American Statistical Association"},{"key":"10.1016\/j.comgeo.2006.05.005_bib020","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jcss.1997.1493","article-title":"Faster shortest-path algorithms for planar graphs","volume":"55","author":"Klein","year":"1997","journal-title":"Journal of Computer and System Sciences"},{"key":"10.1016\/j.comgeo.2006.05.005_bib021","series-title":"Mathematical Software III","first-page":"161","article-title":"Software for C1 surface interpolation","author":"Lawson","year":"1977"},{"key":"10.1016\/j.comgeo.2006.05.005_bib022","series-title":"Complexity Issues in VLSI","author":"Leighton","year":"1983"},{"key":"10.1016\/j.comgeo.2006.05.005_bib023","series-title":"Area Efficient VLSI Computation","author":"Leiserson","year":"1983"},{"key":"10.1016\/j.comgeo.2006.05.005_bib024","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton","year":"1979","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"10.1016\/j.comgeo.2006.05.005_bib025","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","article-title":"Applications of a planar separator theorem","volume":"9","author":"Lipton","year":"1980","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/j.comgeo.2006.05.005_bib026","first-page":"421","article-title":"Geometric range searching","volume":"26","author":"Matou\u0161ek","year":"1999","journal-title":"ACM Computing Surveys"},{"key":"10.1016\/j.comgeo.2006.05.005_bib027","series-title":"Surveys in Combinatorics 1989","first-page":"148","article-title":"On the method of bounded differences","volume":"vol. 141","author":"McDiarmid","year":"1989"},{"key":"10.1016\/j.comgeo.2006.05.005_bib028","series-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","first-page":"195","article-title":"Concentration","volume":"vol. 16","author":"McDiarmid","year":"1998"},{"key":"10.1016\/j.comgeo.2006.05.005_bib029","series-title":"Spatial Tessellations","author":"Okabe","year":"1992"},{"key":"10.1016\/j.comgeo.2006.05.005_bib030","series-title":"Combinatorial Geometry","author":"Pach","year":"1995"},{"key":"10.1016\/j.comgeo.2006.05.005_bib031","series-title":"Handbook of Computational Geometry","first-page":"877","article-title":"Closest-point problems in computational geometry","author":"Smid","year":"2000"},{"key":"10.1016\/j.comgeo.2006.05.005_bib032","series-title":"Handbook of Discrete and Computational Geometry","first-page":"559","article-title":"Point location","author":"Snoeyink","year":"1997"},{"key":"10.1016\/j.comgeo.2006.05.005_bib033","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","article-title":"Multidimensional binary search trees used for associative searching","volume":"18","author":"Bentley","year":"1975","journal-title":"Communications of the ACM"},{"key":"10.1016\/j.comgeo.2006.05.005_bib034","series-title":"Handbook of Algorithms and Data Structures","author":"Gonnet","year":"1991"},{"key":"10.1016\/j.comgeo.2006.05.005_bib035","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1002\/rsa.3240010106","article-title":"The transitive closure of a random digraph","volume":"1","author":"Karp","year":"1990","journal-title":"Random Structures and Algorithms"},{"key":"10.1016\/j.comgeo.2006.05.005_bib036","volume":"vol. 2","author":"Knuth","year":"1981"},{"key":"10.1016\/j.comgeo.2006.05.005_bib037","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1002\/(SICI)1098-2418(199709)11:2<97::AID-RSA1>3.0.CO;2-O","article-title":"The degree sequence of a random graph, I. The models","volume":"11","author":"McKay","year":"1997","journal-title":"Random Structures and Algorithms"},{"key":"10.1016\/j.comgeo.2006.05.005_bib038","series-title":"Computational Geometry in C","author":"O'Rourke","year":"1998"},{"key":"10.1016\/j.comgeo.2006.05.005_bib039","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF02579208","article-title":"Sharp concentration of the chromatic number on random graphs Gn,p","volume":"7","author":"Shamir","year":"1987","journal-title":"Combinatorica"}],"container-title":["Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0925772106000642?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0925772106000642?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,11]],"date-time":"2019-01-11T14:22:00Z","timestamp":1547216520000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0925772106000642"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,2]]}},"alternative-id":["S0925772106000642"],"URL":"https:\/\/doi.org\/10.1016\/j.comgeo.2006.05.005","relation":{},"ISSN":["0925-7721"],"issn-type":[{"value":"0925-7721","type":"print"}],"subject":[],"published":{"date-parts":[[2007,2]]}}}