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

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

Research output: Contribution to journalArticle

82 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)77-105
Number of pages29
JournalTheoretical Computer Science
Volume84
Issue number1
DOIs
StatePublished - Jul 22 1991

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A singly exponential stratification scheme for real semi-algebraic varieties and its applications'. Together they form a unique fingerprint.

  • Cite this