×

On computing a set of points meeting every cell defined by a family of polynomials on a variety. (English) Zbl 0872.68050

Summary: We consider a family of \(s\) polynomial, \({\mathcal P}= \{P_1, \dots, P_s\}\), in \(k\) variables with coefficients in a real closed field \(R\), each of degree at most \(d\), and an algebraic variety \(V\) of real dimension \(k'\) which is defined as the zero set of a polynomial \(Q\) of degree at most \(d\). The number of semi-algebraically connected components of all non-empty sign conditions on \({\mathcal P}\) over \(V\) is bounded by \(s^{k'} (O(d))^k\). In this paper we present a new algorithm to compute a set of points meeting every semi-algebraic connected component of each non-empty sign condition of \({\mathcal P}\) over \(V\). Its complexity is \(s^{k'+1} d^{O(k)}\). This interpolates a sequence of results between the Ben-Or-Kozen-Reif algorithm which is the case \(k'=0\), in one variable, and the Basu-Pollack-Roy algorithm which is the case \(k'=k\). It improves the results where the same problem was solved in time \(s^{k'+1} d^{O (k'k)}\).

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Basu, R. Pollack, M.-F. Roy, A new algorithm to find a point in every cell defined by a family of polynomials, Quantifier Elimination and Cylindrical Algebraic Decomposition, Springer-Verlag, New York/Berlin; S. Basu, R. Pollack, M.-F. Roy, A new algorithm to find a point in every cell defined by a family of polynomials, Quantifier Elimination and Cylindrical Algebraic Decomposition, Springer-Verlag, New York/Berlin · Zbl 0900.68278
[2] Basu, S.; Pollack, R.; Roy, M.-F., On the number of cells defined by a family of polynomials on a variety, (Goldberg, K. Y.; Halperin, D.; Latombe, J.-C.; Wilson, R. H., Algorithmic Foundations of Robotics (1995), Peters: Peters Boston), 537-555 · Zbl 0829.14025
[3] S. Basu, R. Pollack, M.-F. Roy, On the combinatorial and algebraic complexity of quantifier elimination (extended abstract), Proc. 35th IEEE Symposium on Foundations of Computer Science, 1994, 632, 642, Association for Computing Machinery; S. Basu, R. Pollack, M.-F. Roy, On the combinatorial and algebraic complexity of quantifier elimination (extended abstract), Proc. 35th IEEE Symposium on Foundations of Computer Science, 1994, 632, 642, Association for Computing Machinery · Zbl 0885.68070
[4] Basu, S.; Pollack, R.; Roy, M.-F., On the number of cells defined by a family of polynomials on a variety, Mathematika, 43, 120-126 (1996) · Zbl 0853.14028
[5] Ben-Or, M.; Kozen, D.; Reif, J., The complexity of elementary algebra and geometry, J. Comput. System Sci., 32, 251-264 (1986) · Zbl 0634.03031
[6] Bochnak, J.; Coste, M.; Roy, M.-F., Géométrie algébrique réelle (1987), Springer-Verlag: Springer-Verlag New York/Berlin · Zbl 0633.14016
[7] Coste, M.; Roy, M.-F., Thom’s lemma, the coding of real algebraic numbers and the topology of semi-algebraic sets, J. Symbolic Comput., 5, 121-129 (1988) · Zbl 0689.14006
[8] Renegar, J., On the computational complexity and geometry of the first order theory of the reals, J. Symbolic Comput. (1992) · Zbl 0798.68073
[9] M.-F. Roy, N. Vorobjov, Computing the complexification of a semialgebraic set, ISSAC 96; M.-F. Roy, N. Vorobjov, Computing the complexification of a semialgebraic set, ISSAC 96 · Zbl 0918.14020
[10] Walker, 1950, Algebraic Curves, Princeton Univ. Press, Princeton, NJ; Walker, 1950, Algebraic Curves, Princeton Univ. Press, Princeton, NJ · Zbl 0039.37701
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.