{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:31:27Z","timestamp":1758267087572},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1992,7,1]],"date-time":"1992-07-01T00:00:00Z","timestamp":709948800000},"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":[[1992,7]]},"DOI":"10.1007\/bf02293035","type":"journal-article","created":{"date-parts":[[2006,2,14]],"date-time":"2006-02-14T12:50:59Z","timestamp":1139921459000},"page":"51-71","source":"Crossref","is-referenced-by-count":53,"title":["Applications of random sampling to on-line algorithms in computational geometry"],"prefix":"10.1007","volume":"8","author":[{"given":"Jean-Daniel","family":"Boissonnat","sequence":"first","affiliation":[]},{"given":"Olivier","family":"Devillers","sequence":"additional","affiliation":[]},{"given":"Ren\u00e9","family":"Schott","sequence":"additional","affiliation":[]},{"given":"Monique","family":"Teillaud","sequence":"additional","affiliation":[]},{"given":"Mariette","family":"Yvinec","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1992,7,1]]},"reference":[{"key":"BF02293035_CR1","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/B978-0-444-87806-9.50007-4","volume-title":"Computational Geometry","author":"D. Avis","year":"1985","unstructured":"D. Avis, H. ElGindy, and R. Seidel, Simple on-line algorithms for convex polygons,Computational Geometry (G. T. Toussaint, ed.), North-Holland, Amsterdam, 1985, pp. 23\u201342."},{"key":"BF02293035_CR2","unstructured":"J.-D. Boissonnat, O. Devillers, and M. Teillaud, A semi-dynamic construction of higher-order Voronoi diagrams and its randomized analysis,Algorithmica (to appear). Full paper available as Technical Report INRIA 1207. Abstract published inSecond Canadian Conference on Computational Geometry, Ottawa 1990."},{"key":"BF02293035_CR3","doi-asserted-by":"crossref","unstructured":"J.-D. Boissonnat and M. Teillaud, A hierarchical representation of objects: the Delaunay tree,Second ACM Symposium on Computational Geometry, Yorktown Heights, June 1986.","DOI":"10.1145\/10515.10543"},{"key":"BF02293035_CR4","unstructured":"J.-D. Boissonnat and M. Teillaud, On the randomized construction of the Delaunay tree,Theoretical Computer Science (to appear). Full paper available as Technical Report INRIA 1140."},{"key":"BF02293035_CR5","doi-asserted-by":"crossref","unstructured":"B. Chazelle and H. Edelsbrunner, An optimal algorithm for intersecting line segments in the plane,IEEE Symposium on Foundations of Computer Science, 1988, pp. 590\u2013600.","DOI":"10.1109\/SFCS.1988.21975"},{"key":"BF02293035_CR6","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02187783","volume":"5","author":"K. L. Clarkson","year":"1990","unstructured":"K. L. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and surfaces,Discrete and Computational Geometry,5 (1990), 99\u2013160.","journal-title":"Discrete and Computational Geometry"},{"key":"BF02293035_CR7","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson and P. W. Shor, Applications of random sampling in computational geometry, II,Discrete and Computational Geometry,4 (5) (1989).","DOI":"10.1007\/BF02187740"},{"key":"BF02293035_CR8","doi-asserted-by":"crossref","unstructured":"R. A. Dwyer, Higher-dimensional Voronoi diagrams in linear expected time,5th ACM Symposium on Computational Geometry, Saarbr\u00fccken, June 1989.","DOI":"10.1145\/73833.73869"},{"key":"BF02293035_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms on Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner,Algorithms on Combinatorial Geometry, Springer-Verlag, New York, 1987."},{"key":"BF02293035_CR10","first-page":"414","volume-title":"Randomized incremental construction of Delaunay and Voronoi diagrams","author":"L. J. Guibas","year":"1990","unstructured":"L. J. Guibas, D. E. Knuth, and M. Sharir, Randomized incremental construction of Delaunay and Voronoi diagrams,ICALP 90, Springer-Verlag, New York, 1990, pp. 414\u2013431."},{"key":"BF02293035_CR11","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/3-540-52282-4_46","volume-title":"STACS 90","author":"K. Mehlhorn","year":"1990","unstructured":"K. Mehlhorn, S. Meiser, and C. O'D\u00fanlaing, On the construction of abstract Voronoi diagrams,STACS 90 (C. Choffrut and T. Lengauer, eds.), Springer-Verlag, New York, 1990, pp. 227\u2013239."},{"key":"BF02293035_CR12","doi-asserted-by":"crossref","unstructured":"K. Mulmuley, On obstruction in relation to a fixed viewpoint,IEEE Symposium on Foundations of Computer Science, 1989, pp. 592\u2013597.","DOI":"10.1109\/SFCS.1989.63540"},{"key":"BF02293035_CR13","doi-asserted-by":"crossref","unstructured":"R. Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face,ACM Symposium on Theory of Computing, 1986, pp. 404\u2013413.","DOI":"10.1145\/12130.12172"},{"key":"BF02293035_CR14","series-title":"Technical Report","volume-title":"A Convex Hull Algorithm Optimal for Point Sites in Even Dimensions","author":"R. Seidel","year":"1981","unstructured":"R. Seidel, A Convex Hull Algorithm Optimal for Point Sites in Even Dimensions, Technical Report 14, Department of Computer Science, University British Columbia, Vancouver, BC, 1981."},{"key":"BF02293035_CR15","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0020-0190(85)90044-4","volume":"20","author":"E. Welzl","year":"1985","unstructured":"E. Welzl, Constructing the visibility graph forn line segments ino(n 2) time,Information Processing Letters,20 (1985), 167\u2013171.","journal-title":"Information Processing Letters"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02293035.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02293035\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02293035","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T19:03:09Z","timestamp":1557946989000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02293035"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,7]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1992,7]]}},"alternative-id":["BF02293035"],"URL":"https:\/\/doi.org\/10.1007\/bf02293035","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,7]]}}}