Computing roadmaps of semi-algebraic sets on a variety
HTML articles powered by AMS MathViewer
- by Saugata Basu, Richard Pollack and Marie-Françoise Roy;
- J. Amer. Math. Soc. 13 (2000), 55-82
- DOI: https://doi.org/10.1090/S0894-0347-99-00311-2
- Published electronically: July 20, 1999
- PDF | Request permission
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
- 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 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 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 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 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) Lecture Notes in Comput. Sci., Vol. 33, Springer, Berlin-New York, 1975, pp. 134–183. MR 403962
- 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 10.1016/S0747-7171(88)80008-7
- Michel Coste and Masahiro Shiota, Nash triviality in families of Nash manifolds, Invent. Math. 108 (1992), no. 2, 349–368. MR 1161096, DOI 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 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 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 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 10.1007/3-540-54195-0_{5}0
- 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, NJ, 1963. Based on lecture notes by M. Spivak and R. Wells. MR 163331, DOI 10.1515/9781400881802
- 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 10.1016/S0747-7171(10)80003-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 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 10.1016/0196-8858(83)90014-3
Bibliographic 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
- 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. - © Copyright 1999 American Mathematical Society
- 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
- MathSciNet review: 1685780