{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T03:19:31Z","timestamp":1774495171338,"version":"3.50.1"},"reference-count":50,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1991,7,1]],"date-time":"1991-07-01T00:00:00Z","timestamp":678326400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":8052,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1991,7]]},"DOI":"10.1016\/0304-3975(91)90261-y","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T03:47:37Z","timestamp":1027655257000},"page":"77-105","source":"Crossref","is-referenced-by-count":74,"title":["A singly exponential stratification scheme for real semi-algebraic varieties and its applications"],"prefix":"10.1016","volume":"84","author":[{"given":"Bernard","family":"Chazelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Herbert","family":"Edelsbrunner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonidas J.","family":"Guibas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(91)90261-Y_BIB1","author":"Agarwal","year":"1988","journal-title":"Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB2","series-title":"Tech. Rep. 436","article-title":"Algorithms for the geometry of semi-algebraic sets","author":"Arnon","year":"1981"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB3","doi-asserted-by":"crossref","first-page":"878","DOI":"10.1137\/0213055","article-title":"Cylindrical algebraic decomposition II: an adjacency algorithm for the plane","volume":"13","author":"Arnon","year":"1984","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB4","first-page":"381","article-title":"Triangles in space, or building and analyzing castles in the air","author":"Aronov","year":"1988","journal-title":"Proc. 4th Ann. ACM Sympos. Computational Geom."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB5","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1016\/0898-1221(85)90105-1","article-title":"Dynamic computational geometry","volume":"11","author":"Atallah","year":"1985","journal-title":"Comput. Math. Appl."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB6","article-title":"On the number of connected components of a real algebraic set","author":"Bennedetti","year":"1988","journal-title":"Tech. Rept. LMENS-88-11"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB7","series-title":"G\u00e9om\u00e9trie Alg\u00e9brique R\u00e9elle","author":"Bochnak","year":"1987"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB8","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1145\/321662.321665","article-title":"On Euclid's algorithm and the theory of subresultants","volume":"18","author":"Brown","year":"1971","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB9","article-title":"Some new effectivity bounds in computational geometry","author":"Caniglia","year":"1988","journal-title":"Proc. 6th Internat. Conf. on Applied Algebra, Algorithmic and Error Correcting Codes"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB10","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1109\/SFCS.1987.1","article-title":"A new algebraic method for motion planning and real geometry","author":"Canny","year":"1987","journal-title":"Proc. 28th Ann. IEEE Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB11","first-page":"460","article-title":"Some algebraic and geometric computations in PSPACE","author":"Canny","year":"1988","journal-title":"Proc. 20th Ann. ACM Symp. on Theory of Computability"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB12","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1137\/0213031","article-title":"Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm","volume":"13","author":"Chazelle","year":"1984","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB13","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/BF00263295","article-title":"Some techniques for geometric searching with implicit set representations","volume":"24","author":"Chazelle","year":"1987","journal-title":"Acta Inform."},{"issue":"3","key":"10.1016\/0304-3975(91)90261-Y_BIB14","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\/0304-3975(91)90261-Y_BIB15","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/BF02187807","article-title":"Triangulating a nonconvex polytope","volume":"5","author":"Chazelle","year":"1990","journal-title":"Discrete and Computational Geometry"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB16","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0747-7171(08)80065-X","article-title":"An algorithm for generalized point location and its applications","volume":"10","author":"Chazelle","year":"1990","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB17","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\/0304-3975(91)90261-Y_BIB18","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\/0304-3975(91)90261-Y_BIB19","first-page":"1","article-title":"Applications of random sampling in computational geometry, II","author":"Clarkson","year":"1988","journal-title":"Proc. 4th Ann. ACM Sympos. Computational Geometry"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB20","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1109\/SFCS.1988.21973","article-title":"Combinatorial complexity bounds for arrangements of curves and surfaces","author":"Clarkson","year":"1988","journal-title":"Proc. 29th Ann. IEEE Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB21","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0196-6774(86)90004-0","article-title":"Searching and storing similar lists","volume":"7","author":"Cole","year":"1986","journal-title":"J. Algorithms"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB22","series-title":"Proc. 2nd GI Conf. on Automata Theory and Formal Languages","first-page":"134","article-title":"Quantifier elimination for real closed fields by cylindric algebraic decomposition","volume":"33","author":"Collins","year":"1975"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB23","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/800205.806319","article-title":"Polynomial real root isolation by differentiation","author":"Collins","year":"1976","journal-title":"Proc. ACM Symp. on Symbolic and Algebraic Computations"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB24","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0747-7171(88)80008-7","article-title":"Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets","volume":"5","author":"Coste","year":"1988","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB25","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0747-7171(88)80004-X","article-title":"Real quantifier elimination is doubly exponential","volume":"5","author":"Davenport","year":"1988","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB26","series-title":"Algorithms in Combinatorial Geometry","author":"Edelsbrunner","year":"1987"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB27","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1145\/73393.73399","article-title":"The complexity of many faces in arrangements of lines and of segments","author":"Edelsbrunner","year":"1988","journal-title":"Proc. 4th Ann. ACM Sympos. Computational Geometry"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB28","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","article-title":"Optimal point location in a monotone subdivision","volume":"15","author":"Edelsbrunner","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB29","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF02825045","article-title":"Shape determination for real curves and surfaces","volume":"29","author":"Gianni","year":"1983","journal-title":"Ann. Univ. Ferrara Sez. VII N.S."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB30","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","article-title":"Solving systems of polynomial inequalities in subexponential time","volume":"5","author":"Grigor'ev","year":"1988","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB31","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579170","article-title":"Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes","volume":"6","author":"Hart","year":"1986","journal-title":"Combinatorica"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB32","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","article-title":"Epsilon-nets and simplex range queries","volume":"2","author":"Haussler","year":"1987","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB33","first-page":"515","article-title":"Algebraic cell decomposition in NC","author":"Kozen","year":"1985","journal-title":"Proc. 26th Ann. IEEE Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB34","series-title":"Computer Algebra: Symbolic and Algebraic Computation","article-title":"Generalized polynomial remainder sequences","author":"Loos","year":"1983"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB35","series-title":"Computer Algebra: Symbolic and Algebraic Computation","article-title":"Computing in algebraic extensions","author":"Loos","year":"1983"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB36","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1307\/mmj\/1028999140","article-title":"An inequality for the discrimination of a polynomial","volume":"11","author":"Mahler","year":"1964","journal-title":"Michigan Math. J."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB37","series-title":"First Computational Geometry Day","article-title":"The biggest stick problem","author":"McKenna","year":"1986"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB38","doi-asserted-by":"crossref","DOI":"10.1090\/S0002-9939-1964-0161339-9","article-title":"On the Betti numbers of real varieties","volume":"15","author":"Milnor","year":"1964","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB39","series-title":"Algorithms in Combinatorial Geometry","author":"Preparata","year":"1985"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB40","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1137\/0215069","article-title":"On approximations and incidence in cylindrical algebraic decompositions","volume":"15","author":"Prill","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB41","series-title":"Proc. 16th Internat. Conf. Parallel Processing","article-title":"Optimal randomized parallel algorithms for computational geometry","author":"Reif","year":"1987-1988"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB42","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1109\/SFCS.1988.21945","article-title":"A faster PSPACE algorithm for deciding the existential theory of the reals","author":"Renegar","year":"1988","journal-title":"Proc. 29th Ann. IEEE Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB43","article-title":"Computation of the topology of a real algebraic curse","author":"Roy","year":"1987","journal-title":"Proc. Congress on Computational topology and geometry"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB44","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/6138.6151","article-title":"Planar point location using persistent search trees","volume":"29","author":"Sarnak","year":"1986","journal-title":"Comm. ACM"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB45","series-title":"Differential geometry and topology","author":"Schwartz","year":"1968"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB46","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/0196-8858(83)90014-3","article-title":"On the \u201cpiano movers\u201d problem. II: General techniques for computing topological properties of real algebraic manifolds","volume":"4","author":"Schwartz","year":"1983","journal-title":"Adv. in Appl. Math."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB47","unstructured":"M. Spivak, A Comprehensive introduction to differential geometry, Vol. 1 (Publish or Perish, Berkeley)."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB48","series-title":"Modern Algebra","author":"van der Waerden","year":"1950"},{"key":"10.1016\/0304-3975(91)90261-Y_BIB49","doi-asserted-by":"crossref","DOI":"10.2307\/1969908","article-title":"Elementary structure of real algebraic varieties","volume":"66","author":"Whitney","year":"1957","journal-title":"Ann. of Math."},{"key":"10.1016\/0304-3975(91)90261-Y_BIB50","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/0211059","article-title":"On constructing minimum spanning tree in k-dimensional space and related problems","volume":"11","author":"Yao","year":"1982","journal-title":"SIAM J. Comput."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759190261Y?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759190261Y?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,4,18]],"date-time":"2023-04-18T16:39:06Z","timestamp":1681835946000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759190261Y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,7]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1991,7]]}},"alternative-id":["030439759190261Y"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(91)90261-y","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1991,7]]}}}