{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T13:43:44Z","timestamp":1768743824201,"version":"3.49.0"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"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":[[1995,1]]},"DOI":"10.1007\/bf02574027","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T12:15:26Z","timestamp":1174565726000},"page":"41-57","source":"Crossref","is-referenced-by-count":24,"title":["Better lower bounds on detecting affine and spherical degeneracies"],"prefix":"10.1007","volume":"13","author":[{"given":"J.","family":"Erickson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Seidel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1995,1,1]]},"reference":[{"key":"BF02574027_CR1","doi-asserted-by":"crossref","unstructured":"M. Ben-Or. Lower bounds for algebraic computation trees.Proc. 15th Ann. ACM Symp. on Theory of Computing, pages 80\u201386, 1983.","DOI":"10.1145\/800061.808735"},{"key":"BF02574027_CR2","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/BF01934990","volume":"25","author":"B. Chazelle","year":"1985","unstructured":"B. Chazelle, L. J. Guibas, and D. T. Lee. The power of geometric duality.BIT, 25:76\u201390, 1985.","journal-title":"BIT"},{"key":"BF02574027_CR3","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0304-3975(89)90132-1","volume":"66","author":"M. Dietzfelbinger","year":"1989","unstructured":"M. Dietzfelbinger. Lower bounds for sorting of sums.Theoret. Comput. Sci., 66:137\u2013155, 1989.","journal-title":"Theoret. Comput. Sci."},{"key":"BF02574027_CR4","series-title":"EATCS Monographs on Theoretical Computer Science","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. EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, Heidelberg, 1987."},{"key":"BF02574027_CR5","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0022-0000(89)90038-X","volume":"38","author":"H. Edelsbrunner","year":"1989","unstructured":"H. Edelsbrunner and L. J. Guibas. Topologically sweeping an arrangement.J. Comput. System Sci., 38:165\u2013194, 1989. Corrigendum in 42:249\u2013251, 1991.","journal-title":"J. Comput. System Sci."},{"key":"BF02574027_CR6","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications.SIAM J. Comput., 15:341\u2013363, 1986.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"BF02574027_CR7","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1137\/0222031","volume":"22","author":"H. Edelsbrunner","year":"1993","unstructured":"H. Edelsbrunner, R. Seidel, and M. Sharir. On the zone theorem for hyperplane arrangements.SIAM J. Comput., 22(2):418\u2013429, 1993.","journal-title":"SIAM J. Comput."},{"key":"BF02574027_CR8","doi-asserted-by":"crossref","unstructured":"J. Erickson and R. Seidel. Better lower bounds on detecting affine and spherical degeneracies.Proc. 34th Ann. IEEE Symp. on Foundations of Computer Science, pages 528\u2013536, 1993.","DOI":"10.1109\/SFCS.1993.366834"},{"key":"BF02574027_CR9","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0304-3975(76)90078-5","volume":"1","author":"M. L. Fredman","year":"1976","unstructured":"M. L. Fredman. How good is the information theory bound in sorting?Theoret. Comput. Sci., 1:355\u2013361, 1976.","journal-title":"Theoret. Comput. Sci."},{"key":"BF02574027_CR10","series-title":"Report RUU-CS-93-15","volume-title":"n 2-hard problems in computational geometry","author":"A. Gajentaan","year":"1993","unstructured":"A. Gajentaan and M. H. Overmars.n 2-hard problems in computational geometry. Report RUU-CS-93-15, Department of Computer Science, Utrecht University, Utrecht, April 1993."},{"key":"BF02574027_CR11","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1137\/0212032","volume":"12","author":"J. E. Goodman","year":"1983","unstructured":"J. E. Goodman and R. Pollack. Multidimensional sorting.SIAM J. Comput., 12:484\u2013507, 1983.","journal-title":"SIAM J. Comput."},{"key":"BF02574027_CR12","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/978-3-642-58043-7_6","volume-title":"New Trends in Discrete and Computational Geometry","author":"J. E. Goodman","year":"1993","unstructured":"J. E. Goodman and R. Pollack. Allowable sequences and order types in discrete and computational geometry. In J. Pach, editor,New Trends in Discrete and Computational Geometry, pages 103\u2013134, Algorithms and Combinatorics, vol. 10. Springer-Verlag, New York, 1993."},{"key":"BF02574027_CR13","first-page":"639","volume":"3","author":"J. E. Goodman","year":"1990","unstructured":"J. E. Goodman, R. Pollack, and B. Sturmfels. The intrinsic spread of a configuration in \u211d d .J. Amer. Math. Soc., 3:639\u2013651, 1990.","journal-title":"J. Amer. Math. Soc."},{"key":"BF02574027_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","volume":"3","author":"J. M. Steele","year":"1982","unstructured":"J. M. Steele and A. C. Yao. Lower bounds for algebraic decision trees.J. Algorithms, 3:1\u20138, 1982.","journal-title":"J. Algorithms"},{"key":"BF02574027_CR15","first-page":"150","volume":"19","author":"J. Leeuwen van","year":"1983","unstructured":"J. van Leeuwen. Problem P20.Bull. EATCS, 19:150, 1983.","journal-title":"Bull. EATCS"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574027.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02574027\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T16:19:18Z","timestamp":1558196358000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02574027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,1]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,1]]}},"alternative-id":["BF02574027"],"URL":"https:\/\/doi.org\/10.1007\/bf02574027","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,1]]}}}