{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T12:05:36Z","timestamp":1742385936896},"reference-count":47,"publisher":"Elsevier","isbn-type":[{"value":"9780444825377","type":"print"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1016\/b978-044482537-7\/50017-6","type":"book-chapter","created":{"date-parts":[[2007,9,8]],"date-time":"2007-09-08T11:17:56Z","timestamp":1189250276000},"page":"703-724","source":"Crossref","is-referenced-by-count":3,"title":["Randomized Algorithms in Computational Geometry"],"prefix":"10.1016","author":[{"given":"Ketan","family":"Mulmuley","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/B978-044482537-7\/50017-6_bb0010","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF02187805","article-title":"Partitioning arrangements of lines: I. An efficient deterministic algorithm","volume":"5","author":"Agarwal","year":"1990","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0015","first-page":"517","article-title":"Ray shooting and parametric search","author":"Agarwal","year":"1992"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0020","first-page":"142","article-title":"A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams","author":"Aurenhammer","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0025","article-title":"A randomized incremental algorithm for constructing higher order Voronoi diagrams","author":"Boissonnat","year":"1990"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0030","article-title":"On the randomized construction of the Delauney tree","author":"Boissonnat","year":"1989"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0035","first-page":"29","article-title":"An optimal convex hull algorithm and new results on cuttings","author":"Chazelle","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0040","first-page":"441","article-title":"Computing a face in an arrangement of line segments","author":"Chazelle","year":"1991"},{"issue":"3","key":"10.1016\/B978-044482537-7\/50017-6_bb0045","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02122778","article-title":"A deterministic view of random sampling and its use in geometry","volume":"10","author":"Chazelle","year":"1990","journal-title":"Combinatorica"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0050","article-title":"Building Voronoi diagrams for convex polygons in linear expected time","author":"Chew","year":"1985"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0055","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","article-title":"New applications of random sampling in computational geometry","volume":"2","author":"Clarkson","year":"1987","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0060","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1137\/0217052","article-title":"A randomized algorithm for closest-point queries","volume":"17","author":"Clarkson","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0065","series-title":"Computimg in Euclidean Geometry","first-page":"117","article-title":"Randomized geometric algorithms","author":"Clarkson","year":"1992"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0070","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","article-title":"Applications of random sampling in computational geometry, II","volume":"4","author":"Clarkson","year":"1989","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"10.1016\/B978-044482537-7\/50017-6_bb0075","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1142\/S021819599200007X","article-title":"Randomization yields simple O(n log*n) algorithms for difficult \u03a9(n) problems","volume":"2","author":"Devillers","year":"1992","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0080","first-page":"42","article-title":"Fully dynamic Delaunay triangulation in logarithmic expected time per operation","volume":"519","author":"Devillers","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50017-6_rf0085","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF01758770","article-title":"Randomized incremental construction of Delaunay and Voronoi diagrams","volume":"7","author":"Guibas","year":"1992","journal-title":"Algorithmica"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0090","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","article-title":"Epsilon-nets and simplex range queries","volume":"2","author":"Haussier","year":"1987","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0095","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/BF02187804","article-title":"Construction of \u03b5-nets","volume":"5","author":"Matou\u0161ek","year":"1990","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0100","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF02574697","article-title":"Cutting hyperplane arrangements","volume":"6","author":"Matou\u0161ek","year":"1991","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0105","first-page":"276","article-title":"Range searching with efficient hierarchical cuttings","author":"Matou\u0161ek","year":"1992"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0110","first-page":"16","article-title":"Linear optimization queries","author":"Matou\u0161ek","year":"1992"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0115","first-page":"1","article-title":"A subexponential bound for linear programming","author":"Matou\u0161ek","year":"1992"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0120","first-page":"424","article-title":"Discrepancy and \u03b5-approximations for bounded VC-dimension","author":"Matousek","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0125","article-title":"More on cutting arrangements with low crossing number","author":"Matou\u0161ek","year":"1990"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0130","first-page":"505","article-title":"Approximations and optimal geometric divide-and-conquer","author":"Matou\u0161ek","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0135","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BF02574686","article-title":"On the construction of abstract Voronoi diagrams","volume":"6","author":"Mehlhorn","year":"1991","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0140","first-page":"580","article-title":"A fast planar partition algorithm, I","author":"Mulmuley","year":"1988"},{"issue":"3","key":"10.1016\/B978-044482537-7\/50017-6_bb0145","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1145\/74334.74372","article-title":"An efficient algorithm for hidden surface removal","volume":"23","author":"Mulmuley","year":"1989","journal-title":"Comput. Graph. (Proc. ACM SIGGRAPH \u201889)"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0150","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/S0747-7171(08)80064-8","article-title":"A fast planar partition algorithm, I","volume":"10","author":"Mulmuley","year":"1990","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0155","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/102782.102785","article-title":"A fast planar partition algorithm, 11","volume":"38","author":"Mulmuley","year":"1991","journal-title":"J. ACM"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0160","doi-asserted-by":"crossref","first-page":"307338","DOI":"10.1007\/BF02574692","article-title":"On levels in arrangements and Voronoi diagrams","volume":"6","author":"Mulmuley","year":"1991","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0165","first-page":"121","article-title":"Randomized multidimensional search trees: Dynamic sampling","author":"Mulmuley","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0170","first-page":"216","article-title":"Randomized multidimensional search trees: Further results in dynamic sampling","author":"Mulmuley","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0175","first-page":"180","article-title":"Randomized multidimensional search trees: Lazy balancing and dynamic shuffling","author":"Mulmuley","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0180","first-page":"90","article-title":"Randomized geometric algorithms and pseudo-random generators","author":"Mulmuley","year":"1992"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0185","series-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"Mulmuley","year":"1994"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0190","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/BF02293052","article-title":"Dynamic point location in arrangements of hyperplanes","volume":"8","author":"Mulmuley","year":"1992","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"10.1016\/B978-044482537-7\/50017-6_bb0195","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/78973.78977","article-title":"Skip lists: A probabilistic alternative to balanced trees","volume":"33","author":"Pugh","year":"1990","journal-title":"Comm. ACM"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0200","series-title":"Algorithms and Complexity","first-page":"21","article-title":"Probabilistic algorithms","author":"Rabin","year":"1976"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0205","article-title":"Optimal randomized parallel algorithms for computational geometry","author":"Reif","year":"1987"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0210","first-page":"197","article-title":"Dynamic maintenance of geometric structures made easy","author":"Schwarzkopf","year":"1991"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0215","first-page":"211","article-title":"Linear programming and convex hulls made easy","author":"Seidel","year":"1990"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0220","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BF02574699","article-title":"Low dimensional linear programming and convex hulls made easy","volume":"6","author":"Seidel","year":"1991","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0225","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0925-7721(91)90012-4","article-title":"A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons","volume":"1","author":"Seidel","year":"1991","journal-title":"Comput. Geom."},{"key":"10.1016\/B978-044482537-7\/50017-6_rf0230","article-title":"Backwards analysis of randomized geometric algorithms","author":"Seidel","year":"1992"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0235","series-title":"New Trends in Discrete and Computational Geometry","first-page":"37","article-title":"Backward analysis of randomized incremental geometric algorithms","author":"Seidel","year":"1993"},{"key":"10.1016\/B978-044482537-7\/50017-6_bb0240","article-title":"Maintaining arrangements for point location","author":"Sen","year":"1990"}],"container-title":["Handbook of Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:B9780444825377500176?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:B9780444825377500176?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,4]],"date-time":"2019-01-04T07:57:23Z","timestamp":1546588643000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/B9780444825377500176"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9780444825377"],"references-count":47,"URL":"https:\/\/doi.org\/10.1016\/b978-044482537-7\/50017-6","relation":{},"subject":[],"published":{"date-parts":[[2000]]}}}