TY - JOUR
T1 - A singly exponential stratification scheme for real semi-algebraic varieties and its applications
AU - Chazelle, Bernard
AU - Edelsbrunner, Herbert
AU - Guibas, Leonidas J.
AU - Sharir, Micha
N1 - Funding Information:
* The authors wish to thank DEC/Systems Research Center and DEC/Paris Research Laboratory, where part of this research was conducted. For individual support, Bernard Chazelle acknowledges the National Science Foundation for supporting this research in part under Grant CCR-8700917. Herbert Edelsbrunner acknowledges the support of the National Science Foundation under Grant CCR-8714565. Micha Sharir acknowledges the Office of Naval Research under Grant N00014-87-K-0129, the National Science Foundation under Grant No. NSF-DCR-83-20085, grants from the Digital Equipment Corporation and the IBM Corporation, and a research grant from the US-Israeli Binational Science Foundation.
PY - 1991/7/22
Y1 - 1991/7/22
N2 - This paper describes an effective procedure for stratifying a real semi-algebraic set into cells of constant description size. The attractive feature of our method is that the number of cells produced is singly exponential in the number of input variables. This compares favorably with the doubly exponential size of Collins' decomposition. Unlike Collins' construction, however, our scheme does not produce a cell complex but only a smooth stratification. Nevertheless, we are able to apply our results in interesting ways to problems of point location and geometric optimization.
AB - This paper describes an effective procedure for stratifying a real semi-algebraic set into cells of constant description size. The attractive feature of our method is that the number of cells produced is singly exponential in the number of input variables. This compares favorably with the doubly exponential size of Collins' decomposition. Unlike Collins' construction, however, our scheme does not produce a cell complex but only a smooth stratification. Nevertheless, we are able to apply our results in interesting ways to problems of point location and geometric optimization.
UR - http://www.scopus.com/inward/record.url?scp=0026191608&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0026191608&partnerID=8YFLogxK
U2 - 10.1016/0304-3975(91)90261-Y
DO - 10.1016/0304-3975(91)90261-Y
M3 - Article
AN - SCOPUS:0026191608
SN - 0304-3975
VL - 84
SP - 77
EP - 105
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1
ER -