Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

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

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.


References [Enhancements On Off] (What's this?)

  • 1. S. BASU, R. POLLACK, M.-F. ROY On the combinatorial and algebraic complexity of Quantifier Elimination, J. Assoc. Comput. Machin., 43, 1002-1045, (1996). MR 98c:03077
  • 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
  • 3. S. BASU, R. POLLACK, M.-F. ROY On Computing a Set of Points meeting every Semi-algebraically Connected Component of a Family of Polynomials on a Variety , J. Complexity, Vol 13, Number 1, 28-37 (1997). MR 98d:14071
  • 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. J. CANNY, The Complexity of Robot Motion Planning, MIT Press (1987). MR 89m:68142
  • 7. J. CANNY, Computing road maps in general semi-algebraic sets, The Computer Journal, 36: 504-514, (1993). MR 94i:68108
  • 8. J. CANNY, D. GRIGOR'EV, N. VOROBJOV Finding connected components of a semi-algebraic set in subexponential time, Applic. Alg. Eng. Comput. 2: 217-238 (1992). MR 95m:03078
  • 9. G. E. COLLINS, Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Autom. Theor. form. Lang., 2nd GI Conf., Kaiserslautern 1975, Lect. Notes Comput. Sci. 33, 134-183 (1975). MR 53:7771
  • 10. M. COSTE, M.-F. ROY Thom's lemma, the coding of real algebraic numbers and the topology of semi-algebraic sets, J. Symb. Comput. 5, No.1/2, 121-129 (1988). MR 89g:12002
  • 11. M. COSTE, M. SHIOTA Nash triviality in families of Nash manifolds, Invent. Math. 108, 349-368 (1992). MR 93e:14066
  • 12. D. GRIGOR'EV, N. VOROBJOV Counting connected components of a semi-algebraic set in subexponential time, Comput. Complexity 2, No.2, 133-186 (1992). MR 94a:68062
  • 13. L. GOURNAY, J. J. RISLER Construction of roadmaps of semi-algebraic sets, Appl. Algebra Eng. Commun. Comput. 4, No.4, 239-252 (1993). MR 94j:14049
  • 14. R. M. HARDT Semi-algebraic Local Triviality in Semi-algebraic Mappings, Am. J. Math. 102, 291-302 (1980). MR 81d:32012
  • 15. J. HEINTZ, M.-F. ROY, P. SOLERNÒ Single exponential path finding in semi-algebraic sets I: The case of a regular hypersurface, Discrete and Applied Math., Proc.AAECC-8 Tokyo, 1990; Lectures Notes in Comp. Sci. 508, Springer-Verlag 180-186 (1991). MR 92j:14072
  • 16. J. HEINTZ, M.-F. ROY, P. SOLERNÒ Single exponential path finding in semi-algebraic sets II : The general case, Bajaj, Chandrajit L. (ed.), Algebraic geometry and its applications. Collections of papers from Shreeram S. Abhyankar's 60th birthday conference held at Purdue University, West Lafayette, IN, USA, June 1-4, 1990. New York: Springer-Verlag, 449-465 (1994). MR 95i:14054
  • 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, Princeton: Princeton Univ. Press (1963). MR 29:634
  • 19. J. RENEGAR On the computational complexity and geometry of the first order theory of the reals, parts I, II and III., J. Symb. Comput., 13 (3) 255-352, (1992). MR 93h:03011a; MR 93h:03011b; MR 93h:03011c
  • 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.
  • 21. M.-F. ROY, N.N. VOROBJOV Finding irreducible components of some real transcendental varieties, Journal of Computationnal Complexity 4 107-132 (1994). MR 95g:68056
  • 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).
  • 23. J. SCHWARTZ, M. SHARIR On the `piano movers' problem II. General techniques for computing topological properties of real algebraic manifolds, Adv. Appl. Math. 4, 298-351 (1983). MR 85h:52014

Similar Articles

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
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

DOI: https://doi.org/10.1090/S0894-0347-99-00311-2
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

American Mathematical Society