Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
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
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.


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


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: http://dx.doi.org/10.1090/S0894-0347-99-00311-2
PII: S 0894-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