Computing roadmaps of semialgebraic sets on a variety
Authors:
Saugata Basu, Richard Pollack and MarieFrançoise Roy
Journal:
J. Amer. Math. Soc. 13 (2000), 5582
MSC (1991):
Primary 14P10, 68Q25; Secondary 68Q40
Published electronically:
July 20, 1999
MathSciNet review:
1685780
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We consider a semialgebraic set defined by polynomials in variables which is contained in an algebraic variety . The variety is assumed to have real dimension the polynomial and the polynomials defining have degree at most . We present an algorithm which constructs a roadmap on . The complexity of this algorithm is . We also present an algorithm which, given a point of defined by polynomials of degree at most , constructs a path joining this point to the roadmap. The complexity of this algorithm is These algorithms easily yield an algorithm which, given two points of defined by polynomials of degree at most , decides whether or not these two points of lie in the same semialgebraically connected component of and if they do computes a semialgebraic path in connecting the two points.
 1.
Saugata
Basu, Richard
Pollack, and MarieFrançoise
Roy, On the combinatorial and algebraic complexity of quantifier
elimination, J. ACM 43 (1996), no. 6,
1002–1045. MR 1434910
(98c:03077), http://dx.doi.org/10.1145/235809.235813
 2.
S. BASU, R. POLLACK, M.F. ROY Computing Roadmaps of Semialgebraic Sets, Proc. 28th Annual ACM Symposium on the Theory of Computing, 168173, (1996). CMP 97:06
 3.
Saugata
Basu, Richard
Pollack, and MarieFranç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
(98d:14071), http://dx.doi.org/10.1006/jcom.1997.0434
 4.
S. BASU, R. POLLACK, M.F. ROY Computing Roadmaps of Semialgebraic Sets on a Variety, Foundations of Computational Mathematics, F. Cucker and M. Shub, Eds., 115, (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: SpringerVerlag (1998). CMP 99:07
 6.
John
Canny, The complexity of robot motion planning, ACM Doctoral
Dissertation Awards, vol. 1987, MIT Press, Cambridge, MA, 1988. MR 952555
(89m:68142)
 7.
John
Canny, Computing roadmaps of general semialgebraic sets,
Comput. J. 36 (1993), no. 5, 504–514. MR 1234122
(94i:68108), http://dx.doi.org/10.1093/comjnl/36.5.504
 8.
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
(95m:03078), http://dx.doi.org/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. MR 0403962
(53 #7771)
 10.
M.
Coste and M.F.
Roy, Thom’s lemma, the coding of real algebraic numbers and
the computation of the topology of semialgebraic sets, J. Symbolic
Comput. 5 (1988), no. 12, 121–129. MR 949115
(89g:12002), http://dx.doi.org/10.1016/S07477171(88)800087
 11.
Michel
Coste and Masahiro
Shiota, Nash triviality in families of Nash manifolds, Invent.
Math. 108 (1992), no. 2, 349–368. MR 1161096
(93e:14066), http://dx.doi.org/10.1007/BF02100609
 12.
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
(94a:68062), http://dx.doi.org/10.1007/BF01202001
 13.
L.
Gournay and J.J.
Risler, Construction of roadmaps in semialgebraic sets, Appl.
Algebra Engrg. Comm. Comput. 4 (1993), no. 4,
239–252. MR 1235859
(94j:14049), http://dx.doi.org/10.1007/BF01200148
 14.
Robert
M. Hardt, Semialgebraic localtriviality in semialgebraic
mappings, Amer. J. Math. 102 (1980), no. 2,
291–302. MR
564475 (81d:32012), http://dx.doi.org/10.2307/2374240
 15.
Joos
Heintz, MarieFranç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 errorcorrecting codes (Tokyo, 1990) Lecture
Notes in Comput. Sci., vol. 508, Springer, Berlin, 1991,
pp. 180–196. MR 1123950
(92j:14072), http://dx.doi.org/10.1007/3540541950_50
 16.
Joos
Heintz, MarieFrançoise
Roy, and Pablo
Solernó, Single exponential path finding in semialgebraic
sets. II. The general case, Algebraic geometry and its applications
(West Lafayette, IN, 1990), Springer, New York, 1994,
pp. 449–465. MR 1272047
(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, Based on lecture notes by M. Spivak and
R. Wells. Annals of Mathematics Studies, No. 51, Princeton University
Press, Princeton, N.J., 1963. MR 0163331
(29 #634)
 19.
James
Renegar, On the computational complexity and geometry of the
firstorder theory of the reals. I. Introduction. Preliminaries. The
geometry of semialgebraic sets. The decision problem for the existential
theory of the reals, J. Symbolic Comput. 13 (1992),
no. 3, 255–299. MR 1156882
(93h:03011a), http://dx.doi.org/10.1016/S07477171(10)800033
James
Renegar, On the computational complexity and geometry of the
firstorder theory of the reals. II. The general decision problem.
Preliminaries for quantifier elimination, J. Symbolic Comput.
13 (1992), no. 3, 301–327. MR 1156883
(93h:03011b), http://dx.doi.org/10.1016/S07477171(10)800045
James
Renegar, On the computational complexity and geometry of the
firstorder theory of the reals. III. Quantifier elimination, J.
Symbolic Comput. 13 (1992), no. 3, 329–352. MR 1156884
(93h:03011c), http://dx.doi.org/10.1016/S07477171(10)800057
 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.
MarieFrançoise
Roy and Nicolai
Vorobjov, Finding irreducible components of some real
transcendental varieties, Comput. Complexity 4
(1994), no. 2, 107–132. MR 1285473
(95g:68056), http://dx.doi.org/10.1007/BF01202285
 22.
M.F. ROY, N. VOROBJOV Computing the Complexification of a Semialgebraic Set, Proc. of International Symposium on Symbolic and Algebraic Computations, 1996, 2634 (complete version to appear in Math. Zeitschrift).
 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. MR
712908 (85h:52014), http://dx.doi.org/10.1016/01968858(83)900143
 1.
 S. BASU, R. POLLACK, M.F. ROY On the combinatorial and algebraic complexity of Quantifier Elimination, J. Assoc. Comput. Machin., 43, 10021045, (1996). MR 98c:03077
 2.
 S. BASU, R. POLLACK, M.F. ROY Computing Roadmaps of Semialgebraic Sets, Proc. 28th Annual ACM Symposium on the Theory of Computing, 168173, (1996). CMP 97:06
 3.
 S. BASU, R. POLLACK, M.F. ROY On Computing a Set of Points meeting every Semialgebraically Connected Component of a Family of Polynomials on a Variety , J. Complexity, Vol 13, Number 1, 2837 (1997). MR 98d:14071
 4.
 S. BASU, R. POLLACK, M.F. ROY Computing Roadmaps of Semialgebraic Sets on a Variety, Foundations of Computational Mathematics, F. Cucker and M. Shub, Eds., 115, (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: SpringerVerlag (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 semialgebraic sets, The Computer Journal, 36: 504514, (1993). MR 94i:68108
 8.
 J. CANNY, D. GRIGOR'EV, N. VOROBJOV Finding connected components of a semialgebraic set in subexponential time, Applic. Alg. Eng. Comput. 2: 217238 (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, 134183 (1975). MR 53:7771
 10.
 M. COSTE, M.F. ROY Thom's lemma, the coding of real algebraic numbers and the topology of semialgebraic sets, J. Symb. Comput. 5, No.1/2, 121129 (1988). MR 89g:12002
 11.
 M. COSTE, M. SHIOTA Nash triviality in families of Nash manifolds, Invent. Math. 108, 349368 (1992). MR 93e:14066
 12.
 D. GRIGOR'EV, N. VOROBJOV Counting connected components of a semialgebraic set in subexponential time, Comput. Complexity 2, No.2, 133186 (1992). MR 94a:68062
 13.
 L. GOURNAY, J. J. RISLER Construction of roadmaps of semialgebraic sets, Appl. Algebra Eng. Commun. Comput. 4, No.4, 239252 (1993). MR 94j:14049
 14.
 R. M. HARDT Semialgebraic Local Triviality in Semialgebraic Mappings, Am. J. Math. 102, 291302 (1980). MR 81d:32012
 15.
 J. HEINTZ, M.F. ROY, P. SOLERNÒ Single exponential path finding in semialgebraic sets I: The case of a regular hypersurface, Discrete and Applied Math., Proc.AAECC8 Tokyo, 1990; Lectures Notes in Comp. Sci. 508, SpringerVerlag 180186 (1991). MR 92j:14072
 16.
 J. HEINTZ, M.F. ROY, P. SOLERNÒ Single exponential path finding in semialgebraic 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 14, 1990. New York: SpringerVerlag, 449465 (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) 255352, (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 107132 (1994). MR 95g:68056
 22.
 M.F. ROY, N. VOROBJOV Computing the Complexification of a Semialgebraic Set, Proc. of International Symposium on Symbolic and Algebraic Computations, 1996, 2634 (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, 298351 (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
MarieFrançoise Roy
Affiliation:
IRMAR (URA CNRS 305), Université de Rennes, Campus de Beaulieu 35042 Rennes cedex, France
Email:
mfroy@univrennes1.fr
DOI:
http://dx.doi.org/10.1090/S0894034799003112
PII:
S 08940347(99)003112
Keywords:
Roadmaps,
semialgebraic 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 CCR9402640 and CCR9424398.
The second author was supported in part by NSF Grants CCR9402640, CCR9424398, DMS9400293, CCR9711240 and CCR9732101.
The third author was supported in part by the project ESPRITLTR 21024 FRISCO and by European Community contract CHRXCT940506.
Article copyright:
© Copyright 1999
American Mathematical Society
