×

Computing roadmaps of semi-algebraic sets on a variety. (English) Zbl 0933.14037

Summary: We consider a semi-algebraic set \(S\) defined by \(s\) polynomials in \(k\) variables which is contained in an algebraic variety \(Z(Q)\). The variety is assumed to have real dimension \(k',\) the polynomial \(Q\) and the polynomials defining \(S\) have degree at most \(d\). We present an algorithm which constructs a roadmap on \(S\). The complexity of this algorithm is \(s^{k'+1}d^{O(k^2)}\). We also present an algorithm which, given a point of \(S\) defined by polynomials of degree at most \(\tau\), constructs a path joining this point to the roadmap. The complexity of this algorithm is \(k' s \tau^{O(1)} d^{O(k^2)}.\) These algorithms easily yield an algorithm which, given two points of \(S\) defined by polynomials of degree at most \(\tau\), decides whether or not these two points of \(S\) lie in the same semi-algebraically connected component of \(S\) and if they do computes a semi-algebraic path in \(S\) connecting the two points.

MSC:

14P10 Semialgebraic sets and related spaces
68W40 Analysis of algorithms
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Saugata Basu, Richard Pollack, and Marie-Françoise Roy, On the combinatorial and algebraic complexity of quantifier elimination, J. ACM 43 (1996), no. 6, 1002 – 1045. · Zbl 0885.68070 · doi:10.1145/235809.235813
[2] S. BASU, R. POLLACK, M.-F. ROY Computing Roadmaps of Semi-algebraic Sets, Proc. 28th Annual ACM Symposium on the Theory of Computing, 168-173, (1996). CMP 97:06 · Zbl 0917.14028
[3] Saugata Basu, Richard Pollack, and Marie-Françoise Roy, On computing a set of points meeting every cell defined by a family of polynomials on a variety, J. Complexity 13 (1997), no. 1, 28 – 37. · Zbl 0872.68050 · doi:10.1006/jcom.1997.0434
[4] S. BASU, R. POLLACK, M.-F. ROY Computing Roadmaps of Semi-algebraic Sets on a Variety, Foundations of Computational Mathematics, F. Cucker and M. Shub, Eds., 1-15, (1997). CMP 99:05
[5] J. BOCHNAK, M. COSTE, M.-F. ROY Real algebraic geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge, Bd. 36, Berlin: Springer-Verlag (1998). CMP 99:07
[6] John Canny, The complexity of robot motion planning, ACM Doctoral Dissertation Awards, vol. 1987, MIT Press, Cambridge, MA, 1988. · Zbl 0668.14016
[7] John Canny, Computing roadmaps of general semi-algebraic sets, Comput. J. 36 (1993), no. 5, 504 – 514. · Zbl 0798.14031 · doi:10.1093/comjnl/36.5.504
[8] J. Canny, D. Yu. Grigor\(^{\prime}\)ev, and N. N. Vorobjov Jr., Finding connected components of a semialgebraic set in subexponential time, Appl. Algebra Engrg. Comm. Comput. 2 (1992), no. 4, 217 – 238. · Zbl 0783.14036 · doi:10.1007/BF01614146
[9] George E. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975), Springer, Berlin, 1975, pp. 134 – 183. Lecture Notes in Comput. Sci., Vol. 33. · Zbl 0318.02051
[10] M. Coste and M.-F. Roy, Thom’s lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets, J. Symbolic Comput. 5 (1988), no. 1-2, 121 – 129. · Zbl 0689.14006 · doi:10.1016/S0747-7171(88)80008-7
[11] Michel Coste and Masahiro Shiota, Nash triviality in families of Nash manifolds, Invent. Math. 108 (1992), no. 2, 349 – 368. · Zbl 0801.14017 · doi:10.1007/BF02100609
[12] D. Yu. Grigor\(^{\prime}\)ev and N. N. Vorobjov Jr., Counting connected components of a semialgebraic set in subexponential time, Comput. Complexity 2 (1992), no. 2, 133 – 186. · Zbl 0900.68253 · doi:10.1007/BF01202001
[13] L. Gournay and J.-J. Risler, Construction of roadmaps in semi-algebraic sets, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 4, 239 – 252. · Zbl 0807.14047 · doi:10.1007/BF01200148
[14] Robert M. Hardt, Semi-algebraic local-triviality in semi-algebraic mappings, Amer. J. Math. 102 (1980), no. 2, 291 – 302. · Zbl 0465.14012 · doi:10.2307/2374240
[15] Joos Heintz, Marie-Françoise Roy, and Pablo Solernó, Single exponential path finding in semialgebraic sets. I. The case of a regular bounded hypersurface, Applied algebra, algebraic algorithms and error-correcting codes (Tokyo, 1990) Lecture Notes in Comput. Sci., vol. 508, Springer, Berlin, 1991, pp. 180 – 196. · Zbl 0764.14023 · doi:10.1007/3-540-54195-0_50
[16] Joos Heintz, Marie-Françoise Roy, and Pablo Solernó, Single exponential path finding in semi-algebraic sets. II. The general case, Algebraic geometry and its applications (West Lafayette, IN, 1990) Springer, New York, 1994, pp. 449 – 465. · Zbl 0921.14039
[17] J.-C. LATOMBE Robot Motion Planning, The Kluwer International Series in Engineering and Computer Science. 124. Dordrecht: Kluwer Academic Publishers Group (1991).
[18] J. Milnor, Morse theory, Based on lecture notes by M. Spivak and R. Wells. Annals of Mathematics Studies, No. 51, Princeton University Press, Princeton, N.J., 1963. · Zbl 0108.10401
[19] James Renegar, On the computational complexity and geometry of the first-order theory of the reals. I. Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, J. Symbolic Comput. 13 (1992), no. 3, 255 – 299. , https://doi.org/10.1016/S0747-7171(10)80003-3 James Renegar, On the computational complexity and geometry of the first-order theory of the reals. II. The general decision problem. Preliminaries for quantifier elimination, J. Symbolic Comput. 13 (1992), no. 3, 301 – 327. , https://doi.org/10.1016/S0747-7171(10)80004-5 James Renegar, On the computational complexity and geometry of the first-order theory of the reals. III. Quantifier elimination, J. Symbolic Comput. 13 (1992), no. 3, 329 – 352. , https://doi.org/10.1016/S0747-7171(10)80005-7 James Renegar, On the computational complexity and geometry of the first-order theory of the reals. I. Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, J. Symbolic Comput. 13 (1992), no. 3, 255 – 299. , https://doi.org/10.1016/S0747-7171(10)80003-3 James Renegar, On the computational complexity and geometry of the first-order theory of the reals. II. The general decision problem. Preliminaries for quantifier elimination, J. Symbolic Comput. 13 (1992), no. 3, 301 – 327. , https://doi.org/10.1016/S0747-7171(10)80004-5 James Renegar, On the computational complexity and geometry of the first-order theory of the reals. III. Quantifier elimination, J. Symbolic Comput. 13 (1992), no. 3, 329 – 352. , https://doi.org/10.1016/S0747-7171(10)80005-7 James Renegar, On the computational complexity and geometry of the first-order theory of the reals. I. Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, J. Symbolic Comput. 13 (1992), no. 3, 255 – 299. , https://doi.org/10.1016/S0747-7171(10)80003-3 James Renegar, On the computational complexity and geometry of the first-order theory of the reals. II. The general decision problem. Preliminaries for quantifier elimination, J. Symbolic Comput. 13 (1992), no. 3, 301 – 327. , https://doi.org/10.1016/S0747-7171(10)80004-5 James Renegar, On the computational complexity and geometry of the first-order theory of the reals. III. Quantifier elimination, J. Symbolic Comput. 13 (1992), no. 3, 329 – 352. · Zbl 0798.68073 · doi:10.1016/S0747-7171(10)80005-7
[20] F. ROUILLIER, M.-F. ROY, M. SAFEY Finding at least a point in each connected component of a real algebraic set defined by a single equation, to appear in Journal of Complexity. · Zbl 1009.14010
[21] Marie-Françoise Roy and Nicolai Vorobjov, Finding irreducible components of some real transcendental varieties, Comput. Complexity 4 (1994), no. 2, 107 – 132. · Zbl 0808.68065 · doi:10.1007/BF01202285
[22] M.-F. ROY, N. VOROBJOV Computing the Complexification of a Semi-algebraic Set, Proc. of International Symposium on Symbolic and Algebraic Computations, 1996, 26-34 (complete version to appear in Math. Zeitschrift). · Zbl 0918.14020
[23] Jacob T. Schwartz and Micha Sharir, On the ”piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds, Adv. in Appl. Math. 4 (1983), no. 3, 298 – 351. · Zbl 0554.51008 · doi:10.1016/0196-8858(83)90014-3
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.