A singly exponential stratification scheme for real semi-algebraic varieties and its applications
Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1991. A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theoretical Computer Science. 84(1), 77–105.
Download (ext.)
Journal Article
| Published
| English
Scopus indexed
Author
Chazelle, Bernard;
Edelsbrunner, HerbertISTA 
;
Guibas, Leonidas;
Sharir, Micha
;
Guibas, Leonidas;
Sharir, MichaAbstract
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.
Publishing Year
Date Published
1991-07-22
Journal Title
Theoretical Computer Science
Publisher
Elsevier
Acknowledgement
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.
Volume
84
Issue
1
Page
77 - 105
ISSN
eISSN
IST-REx-ID
Cite this
Chazelle B, Edelsbrunner H, Guibas L, Sharir M. A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theoretical Computer Science. 1991;84(1):77-105. doi:10.1016/0304-3975(91)90261-Y
Chazelle, B., Edelsbrunner, H., Guibas, L., & Sharir, M. (1991). A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(91)90261-Y
Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir. “A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications.” Theoretical Computer Science. Elsevier, 1991. https://doi.org/10.1016/0304-3975(91)90261-Y.
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “A singly exponential stratification scheme for real semi-algebraic varieties and its applications,” Theoretical Computer Science, vol. 84, no. 1. Elsevier, pp. 77–105, 1991.
Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1991. A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theoretical Computer Science. 84(1), 77–105.
Chazelle, Bernard, et al. “A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications.” Theoretical Computer Science, vol. 84, no. 1, Elsevier, 1991, pp. 77–105, doi:10.1016/0304-3975(91)90261-Y.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar