Computing roadmaps of semi-algebraic sets on a variety

Basu, Saugata¹ ; Pollack, Richard² ; Roy, Marie-Françoise³

¹ Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109
² Courant Institute of Mathematical Sciences, New York University, New York, New York 10012
³ IRMAR (URA CNRS 305), Université de Rennes, Campus de Beaulieu 35042 Rennes cedex, France

Journal of the American Mathematical Society, Tome 13 (2000) no. 1, pp. 55-82

Résumé

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.

Détail

DOI : 10.1090/S0894-0347-99-00311-2

Bibliographie

[1] Basu, Saugata, Pollack, Richard, Roy, Marie-Franã§Oise On the combinatorial and algebraic complexity of quantifier elimination J. ACM 1996 1002 1045

[2] Basu, Saugata, Pollack, Richard, Roy, Marie-Franã§Oise On computing a set of points meeting every cell defined by a family of polynomials on a variety J. Complexity 1997 28 37

[3] Canny, John The complexity of robot motion planning 1988

[4] Canny, John Computing roadmaps of general semi-algebraic sets Comput. J. 1993 504 514

[5] Canny, J., Grigor′Ev, D. Yu., Vorobjov, N. N., Jr. Finding connected components of a semialgebraic set in subexponential time Appl. Algebra Engrg. Comm. Comput. 1992 217 238

[6] Collins, George E. Quantifier elimination for real closed fields by cylindrical algebraic decomposition 1975 134 183

[7] Coste, M., Roy, M.-F. Thom’s lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets J. Symbolic Comput. 1988 121 129

[8] Coste, Michel, Shiota, Masahiro Nash triviality in families of Nash manifolds Invent. Math. 1992 349 368

[9] Grigor′Ev, D. Yu., Vorobjov, N. N., Jr. Counting connected components of a semialgebraic set in subexponential time Comput. Complexity 1992 133 186

[10] Gournay, L., Risler, J.-J. Construction of roadmaps in semi-algebraic sets Appl. Algebra Engrg. Comm. Comput. 1993 239 252

[11] Hardt, Robert M. Semi-algebraic local-triviality in semi-algebraic mappings Amer. J. Math. 1980 291 302

[12] Heintz, Joos, Roy, Marie-Franã§Oise, Solernã³, Pablo Single exponential path finding in semialgebraic sets. I. The case of a regular bounded hypersurface 1991 180 196

[13] Heintz, Joos, Roy, Marie-Franã§Oise, Solernã³, Pablo Single exponential path finding in semi-algebraic sets. II. The general case 1994 449 465

[14] Milnor, J. Morse theory 1963

[15] Renegar, James 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. 1992 255 299

[16] Roy, Marie-Franã§Oise, Vorobjov, Nicolai Finding irreducible components of some real transcendental varieties Comput. Complexity 1994 107 132

[17] Schwartz, Jacob T., Sharir, Micha On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds Adv. in Appl. Math. 1983 298 351