A singly exponential stratification scheme for real semi-algebraic varieties and its applications

B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Theoretical Computer Science 84 (1991) 77–105.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ; ;
Abstract
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
Volume
84
Issue
1
Page
77 - 105
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, 84(1), 77–105. 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 84, no. 1 (1991): 77–105. 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, 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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar