{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:01Z","timestamp":1725664081374},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582182"},{"type":"electronic","value":"9783540485773"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58218-5_23","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:37:01Z","timestamp":1330270621000},"page":"252-254","source":"Crossref","is-referenced-by-count":0,"title":["Randomized geometric algorithms (abstract)"],"prefix":"10.1007","author":[{"given":"Ketan","family":"Mulmuley","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"23_CR1","first-page":"21","volume-title":"Algorithms and Complexity","author":"M. O. Rabin","year":"1976","unstructured":"M. O. Rabin. Probabilistic algorithms. In J. F. Traub, editor, Algorithms and Complexity, pages 21\u201330. Academic Press, New York, 1976."},{"key":"23_CR2","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. L. Clarkson","year":"1987","unstructured":"K. L. Clarkson. New applications of random sampling in computational geometry. Discrete & Computational Geometry, 2:195\u2013222, 1987.","journal-title":"Discrete & Computational Geometry"},{"key":"23_CR3","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete & Computational Geometry, 2:127\u2013151, 1987.","journal-title":"Discrete & Computational Geometry"},{"key":"23_CR4","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. L. Clarkson","year":"1989","unstructured":"K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete & Computational Geometry, 4:387\u2013421, 1989.","journal-title":"Discrete & Computational Geometry"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. A fast planar partition algorithm, I. In 29th Annual IEEE Symposium on the Foundations Of Computer Science, pages 580\u2013589, 1988.","DOI":"10.1109\/SFCS.1988.21974"},{"key":"23_CR6","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/BF02293052","volume":"8","author":"K. Mulmuley","year":"1992","unstructured":"K. Mulmuley and S. Sen. Dynamic point location in arrangements of hyperplanes. Discrete & Computational Geometry, 8:335\u2013360, 1992.","journal-title":"Discrete & Computational Geometry"},{"issue":"6","key":"23_CR7","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W. Pngh","year":"1990","unstructured":"W. Pngh. Skip lists: A probabilistic alternative to balanced trees. Commun. ACM, 33(6):668\u2013676, 1990.","journal-title":"Commun. ACM"},{"key":"23_CR8","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4:373\u2013395, 1984.","journal-title":"Combinatorica"},{"key":"23_CR9","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"L. G. Khachiyan","year":"1980","unstructured":"L. G. Khachiyan. Polynomial algorithms in linear programming. U.S.S.R. Comput. Math. and Math. Phys., 20:53\u201372, 1980.","journal-title":"U.S.S.R. Comput. Math. and Math. Phys."},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"R. Seidel. Linear programming and convex hulls made easy. In 6th Annual ACM Symposium on Computational Geometry, pages 211\u2013215, 1990.","DOI":"10.1145\/98524.98570"},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. In 8th Annual ACM Symposium on Computational Geometry, pages 1\u20138, 1992.","DOI":"10.1145\/142675.142678"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, M. Sharir, and E. Welzl. Tail estimates for the space complexity of randomized incremental algorithms. In 3rd Annual ACM Symposium On Discrete Algorithms, pages 89\u201393, 1992.","DOI":"10.1016\/0925-7721(93)90011-T"},{"key":"23_CR13","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0304-3975(91)90261-Y","volume":"84","author":"B. Chazelle","year":"1991","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. A singly-exponential stratification scheme for real semi-algebraic varieties and its applications. Theoret. Comput. Sci., 84:77\u2013105, 1991.","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"J. H. Reif and S. Sen. Polling: A new randomized sampling technique for computational geometry. In 21st Annual ACM Symposium on Theory Of Computing, pages 394\u2013404, 1989.","DOI":"10.1145\/73007.73045"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58218-5_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:18:48Z","timestamp":1605647928000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}