Complexity of computing semi-algebraic descriptions of the connected components of a semi-algebraic set

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Complexity of computing semi-algebraic descriptions of the connected components of a semi-algebraic set

Full text

Pdf (224 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1998 international symposium on Symbolic and algebraic computation table of contents

Rostock, Germany

Pages: 25 - 29

Year of Publication: 1998

ISBN:1-58113-002-3

Authors

Saugata Basu	Mathematical Sciences Department, IBM T.J. Watson Research Center, Yorktown Heights, NY
Richard Pollack	Department of Mathematics, Courant Institute of Mathematical Sciences, New York University, New York, NY
Marie-Françoise Roy	IRMAR (URA CNRS 305), Université de Rennes, Campus de Beaulieu 35042, Rennes cedex, France

Sponsors

German Comp Soc : GI - Gesellshaft for Informatik
SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 12, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/281508.281533 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. Basu , R. Pollack , M.-F. Roy, Computing roadmaps of semi-algebraic sets (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.168-173, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237857]
	2	Saugata Basu , Richard Pollack , Marie-Françoise Roy, On the combinatorial and algebraic complexity of quantifier elimination, Journal of the ACM (JACM), v.43 n.6, p.1002-1045, Nov. 1996 [doi>10.1145/235809.235813]
	3	Saugata Basu , Richard Pollack , Marie-Françoise Roy, Computing roadmaps of semi-algebraic sets on a variety (extended abstract), Selected papers of a conference on Foundations of computational mathematics, p.1-15, September 1997, Rio de Janeiro, Brazil
	4	Saugata Basu , Richard Pollack , Marie-Françoise Roy, On computing a set of points meeting every cell defined by a family of polynomials on a variety, Journal of Complexity, v.13 n.1, p.28-37, March 1997 [doi>10.1006/jcom.1997.0434]
	5	S. BASU, R. POLLACK, M.-F. ROY Computing Roadmaps of Semi-algebraic Sets on a VarietyF submittedF preprint available at http: / / www. m at h. nyu. edu / faculty / pollack /in dex. ht ml.
	6	J. BOCHNAK, M. COSTE, M.-F. RoY G~om~trie alg~brique r~elle. Springer-Verlag (1987).
	7	J. CANNYFThe Complexity of Robot Motion PlanningF MIT Press (1987).
	8	J. CANNYF Computing road maps in general semialgebraic setsF The Computer Journal, 36: 504-514F (1993).
	9	J. CANNY, D. GRIGOR'EV, N. VOROBJOV. Finding connected components of a semi-algebraic set in subexponential timeFAppl. Algebra Eng. Commun. Comput.F 2F No.4F 217-238 (1992).
	10	G. E. COLLINS, Quantifier elimination for real closed fields by cylindrical algebraic decompositionFLect. Notes in Comp. Sci.F 33F 515-532F Springerel~Iag (1975).
	11	Michel Coste, Effective Semialgebraic Geometry, Proceedings of the Workshop on Geometry and Robotics, p.1-27, May 26-28, 1988
	12	D. Yu. Grigor'ev , N. N. Vorobjov, Jr., Counting connected components of a semialgebraic set in subexponential time, Computational Complexity, v.2 n.2, p.133-186, 1992 [doi>10.1007/BF01202001]
	13	J. HEINTZ, M.-F. RoY, P. SOLERNb Single exponentim path finding in semi-algebraic sets II: The general case Algebraic geometry and its applicationsF C. L. Bajaj editorF Springer Yrlag (1993) 467-481.
	14	J. HEINTZ, M.-F. RoY, P. SOLERNb Description of the Connected Components of a Semialgebraic Set in Single Exponential TimeF Discrete and Computational Geometry 11:121-140 (1994).
	15	L. GOURNAY, J. J. RISLER Construction of roadmaps of semi-algebraic sets. Journal AAECC 4 239-252 (1993).
	16	J. SCHWARTZ, M. SHARIR, On the 'piano movers' problem II. General techniques for computing topological properties of real algebraic manifoldsF Advances in Applied Mathematics, 4F 298-351 (1983).

CITED BY 4

	Saugata Basu, New results on quantifier elimination over real closed fields and applications to constraint databases, Journal of the ACM (JACM), v.46 n.4, p.537-555, July 1999
	Robert-Paul Berretty , Ken Goldberg , Mark H. Overmars , A. Frank van der Stappen, Geometric algorithms for trap design, Proceedings of the fifteenth annual symposium on Computational geometry, p.95-104, June 13-16, 1999, Miami Beach, Florida, United States
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	B. Bank , M. Giusti , J. Heintz , L. M. Pardo, Generalized polar varieties: geometry and algorithms, Journal of Complexity, v.21 n.4, p.377-412, August 2005