Computing roadmaps of semi-algebraic sets on a variety

Authors:
Saugata Basu, Richard Pollack and Marie-Françoise Roy

Journal:
J. Amer. Math. Soc. **13** (2000), 55-82

MSC (1991):
Primary 14P10, 68Q25; Secondary 68Q40

DOI:
https://doi.org/10.1090/S0894-0347-99-00311-2

Published electronically:
July 20, 1999

MathSciNet review:
1685780

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

- 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. MR**1434910**, DOI https://doi.org/10.1145/235809.235813 - 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). - 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. MR**1449758**, DOI https://doi.org/10.1006/jcom.1997.0434 - 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). - J. Bochnak, M. Coste, M.-F. Roy Real algebraic geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge, Bd. 36, Berlin: Springer-Verlag (1998).
- John Canny,
*The complexity of robot motion planning*, ACM Doctoral Dissertation Awards, vol. 1987, MIT Press, Cambridge, MA, 1988. MR**952555** - John Canny,
*Computing roadmaps of general semi-algebraic sets*, Comput. J.**36**(1993), no. 5, 504–514. MR**1234122**, DOI https://doi.org/10.1093/comjnl/36.5.504 - J. Canny, D. Yu. Grigor′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. MR**1325530**, DOI https://doi.org/10.1007/BF01614146 - 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. MR**0403962** - 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. MR**949115**, DOI https://doi.org/10.1016/S0747-7171%2888%2980008-7 - Michel Coste and Masahiro Shiota,
*Nash triviality in families of Nash manifolds*, Invent. Math.**108**(1992), no. 2, 349–368. MR**1161096**, DOI https://doi.org/10.1007/BF02100609 - D. Yu. Grigor′ev and N. N. Vorobjov Jr.,
*Counting connected components of a semialgebraic set in subexponential time*, Comput. Complexity**2**(1992), no. 2, 133–186. MR**1190827**, DOI https://doi.org/10.1007/BF01202001 - L. Gournay and J.-J. Risler,
*Construction of roadmaps in semi-algebraic sets*, Appl. Algebra Engrg. Comm. Comput.**4**(1993), no. 4, 239–252. MR**1235859**, DOI https://doi.org/10.1007/BF01200148 - Robert M. Hardt,
*Semi-algebraic local-triviality in semi-algebraic mappings*, Amer. J. Math.**102**(1980), no. 2, 291–302. MR**564475**, DOI https://doi.org/10.2307/2374240 - 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. MR**1123950**, DOI https://doi.org/10.1007/3-540-54195-0_50 - 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. MR**1272047** - J.-C. Latombe
*Robot Motion Planning*, The Kluwer International Series in Engineering and Computer Science. 124. Dordrecht: Kluwer Academic Publishers Group (1991). - J. Milnor,
*Morse theory*, Annals of Mathematics Studies, No. 51, Princeton University Press, Princeton, N.J., 1963. Based on lecture notes by M. Spivak and R. Wells. MR**0163331** - 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. MR**1156882**, DOI https://doi.org/10.1016/S0747-7171%2810%2980003-3 - 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. - Marie-Françoise Roy and Nicolai Vorobjov,
*Finding irreducible components of some real transcendental varieties*, Comput. Complexity**4**(1994), no. 2, 107–132. MR**1285473**, DOI https://doi.org/10.1007/BF01202285 - 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). - 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. MR**712908**, DOI https://doi.org/10.1016/0196-8858%2883%2990014-3

Retrieve articles in *Journal of the American Mathematical Society*
with MSC (1991):
14P10,
68Q25,
68Q40

Retrieve articles in all journals with MSC (1991): 14P10, 68Q25, 68Q40

Additional Information

**Saugata Basu**

Affiliation:
Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109

MR Author ID:
351826

Email:
saugata@math.lsa.umich.edu

**Richard Pollack**

Affiliation:
Courant Institute of Mathematical Sciences, New York University, New York, New York 10012

Email:
pollack@cims.nyu.edu

**Marie-Françoise Roy**

Affiliation:
IRMAR (URA CNRS 305), Université de Rennes, Campus de Beaulieu 35042 Rennes cedex, France

Email:
mfroy@univ-rennes1.fr

Keywords:
Roadmaps,
semi-algebraic sets,
variety

Received by editor(s):
November 25, 1997

Received by editor(s) in revised form:
April 14, 1999

Published electronically:
July 20, 1999

Additional Notes:
The first author was supported in part by NSF Grants CCR-9402640 and CCR-9424398.

The second author was supported in part by NSF Grants CCR-9402640, CCR-9424398, DMS-9400293, CCR-9711240 and CCR-9732101.

The third author was supported in part by the project ESPRIT-LTR 21024 FRISCO and by European Community contract CHRX-CT94-0506.

Article copyright:
© Copyright 1999
American Mathematical Society