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

From MaRDI portal
scientific article
Language Label Description Also known as
English
A singly exponential stratification scheme for real semi-algebraic varieties and its applications
scientific article

    Statements

    A singly exponential stratification scheme for real semi-algebraic varieties and its applications (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    26 June 1992
    0 references
    The paper is, according to the authors, another step in the direction of providing singly exponential algorithms for specific real algebraic geometry problems. The main result is a stratification algorithm that gives a stratification of the real affine \(d\)-dimensional space, sign invariant with respect to a given family of \(n\) polynomials in \(d\) variables, which has \(O(n^{2d-2})\) number of cells (therefore singly exponential with respect to the number of variables), having each cell a constant description size. This number of cells is a major improvement if compared to the number of cells (doubly exponential) produced by Collin's algorithm, of a more general purpose. Moreover, it is closer to Milnor's optimal bound \(O(n^ d)\). The whole algorithm presented in this paper is also singly exponential in time, but produces polynomials which are of doubly exponential degree (in the dimension of the space). On the other hand the cell decomposition produced here has not as good topological properties as in the case of Collin's algorithm, but suffices for the applications regarded by the authors: i.e. preprocessing a set of given real algebraic varieties (each one described by a polynomial of the above mentioned family) to support a fast point location. The resulting method allows to improve current solutions for a variety of optimization problems in computational geometry.
    0 references
    0 references
    0 references
    0 references
    0 references
    singly exponential algorithms for real algebraic geometry problems
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references