{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:08:31Z","timestamp":1725455311650},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540605737"},{"type":"electronic","value":"9783540477662"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0015410","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:50:06Z","timestamp":1131864606000},"page":"72-81","source":"Crossref","is-referenced-by-count":2,"title":["Some geometric lower bounds"],"prefix":"10.1007","author":[{"given":"Hank","family":"Chien","sequence":"first","affiliation":[]},{"given":"William","family":"Steiger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"M. Ben-Or. \u201cLower Bounds for Algebraic Computation Trees\u201d. Proc. 15 th STOC, (1983) 80\u201386.","DOI":"10.1145\/800061.808735"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"A. Bj\u00f6rner, L. Lov\u00e1sz, and A. Yao. \u201cLinear Decision Trees: Volume estimates and Topological Bounds\u201d. Proc. 24 th STOC, (1992) 170\u2013177.","DOI":"10.1145\/129712.129730"},{"key":"9_CR3","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1137\/0218055","volume":"18","author":"R. Cole","year":"1989","unstructured":"R. Cole, J. Salowe, W. Steiger, and E. Szemer\u00e9di. \u201cAn Optimal Time Algorithm for Slope Selection\u201d, SIAM J. Comp. 18, (1989) 792\u2013810.","journal-title":"SIAM J. Comp."},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"D. Dobkin and R. Lipton. \u201cOn the Complexity of Computations under Varying Sets of Primitives\u201d. Lecture Notes in Computer Science 33, 110\u2013117, H. Bradhage, Ed., Springer-Verlag, 1975.","DOI":"10.1007\/3-540-07407-4_14"},{"key":"9_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin, 1987."},{"key":"9_CR6","unstructured":"H. Edelsbrunner. pers. com. 1986."},{"key":"9_CR7","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1080\/01621459.1990.10475313","volume":"85","author":"H. Edelsbrunner","year":"1990","unstructured":"H. Edelsbrunner and D. Souvaine. \u201cComputing Least Median of Squares Regression Lines and Guided Topological Sweep\u201d. J. Amer. Statist. Assoc. 85 (1990) 115\u2013119.","journal-title":"J. Amer. Statist. Assoc."},{"key":"9_CR8","unstructured":"Chi-Yuan Lo and W. Steiger. \u201cAn Optimal-Time Algorithm for Ham-Sandwich Cuts in the Plane\u201d. Second Canadian Conference on Computational Geometry, (1990), 5\u20139."},{"key":"9_CR9","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/BF02574017","volume":"11","author":"C. Lo","year":"1994","unstructured":"Chi-Yuan Lo, J. Matou\u0161ek, and W. Steiger. \u201cAlgorithms for Ham-sandwich Cuts\u201d. Discrete and Comp. Geom. 11, (1994) 433\u2013452","journal-title":"Discrete and Comp. Geom."},{"key":"9_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F.P. Preparata","year":"1985","unstructured":"F.P. Preparata and Shamos, M.I. Computational Geometry. Springer-Verlag, New York, NY, 1985."},{"key":"9_CR11","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1080\/01621459.1984.10477105","volume":"79","author":"P. Rousseeuw","year":"1984","unstructured":"P. Rousseeuw. \u201cLeast Median of Squares Regression\u201d. J. Amer. Statist. Assoc. 79 (1984) 871\u2013880.","journal-title":"J. Amer. Statist. Assoc."},{"key":"9_CR12","doi-asserted-by":"crossref","DOI":"10.1002\/0471725382","volume-title":"Robust Regression and Outlier Detection","author":"P. Rousseeuw","year":"1987","unstructured":"P. Rousseeuw and A. Leroy. Robust Regression and Outlier Detection. John Wiley, New York, 1987."},{"key":"9_CR13","doi-asserted-by":"crossref","first-page":"794","DOI":"10.1080\/01621459.1987.10478500","volume":"82","author":"D. Souvaine","year":"1987","unstructured":"D. Souvaine and M. Steele. \u201cEfficient Time and Space Algorithms for Least Median of Squares Regression\u201d. J. Amer. Statist. Assoc. 82 (1987) 794\u2013801.","journal-title":"J. Amer. Statist. Assoc."},{"key":"9_CR14","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0166-218X(86)90009-0","volume":"14","author":"M. Steele","year":"1986","unstructured":"M. Steele and W. Steiger. \u201cAlgorithms and Complexity for Least Median of Squares\u201d. Regression. Discrete Applied Math. 14, (1986) 93\u2013100.","journal-title":"Discrete Applied Math."},{"key":"9_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","volume":"3","author":"M. Steele","year":"1982","unstructured":"M. Steele and A. Yao. \u201cLower Bounds For Algebraic Decision Trees\u201d. J. Algorithms 3, (1982) 1\u20138.","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computations"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0015410","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T02:49:29Z","timestamp":1554432569000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0015410"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540605737","9783540477662"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/bfb0015410","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}