Abstract:
This paper is devoted to the following result: let R be a real closed field and let S be a semialgebraic subset of Rn defined by a boolean combination of polynomial inequalities. Let D be the sum of the degrees of the polynomials involved. Then it is possible to find algorithmically a description of the semialgebraically connected components of S in sequential time Dn o(1) and parallel time (n log D)o(1) This implies that the problem of finding the connected components of a semialgebraic set can be solved in P-SPACE. © 1994 Springer-Verlag New York Inc.
Registro:
Documento: |
Artículo
|
Título: | Description of the connected components of a semialgebraic set in single exponential time |
Autor: | Heintz, J.; Roy, M.-F.; Solernó, P. |
Filiación: | Departmento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Universitaria, Pabellón I, Buenos Aires, 1428, Argentina IRMAR, Université de Rennes I, Rennes Cedex, 35 042, France
|
Año: | 1994
|
Volumen: | 11
|
Número: | 1
|
Página de inicio: | 121
|
Página de fin: | 140
|
DOI: |
http://dx.doi.org/10.1007/BF02573999 |
Título revista: | Discrete & Computational Geometry
|
Título revista abreviado: | Discrete Comput Geom
|
ISSN: | 01795376
|
PDF: | https://bibliotecadigital.exactas.uba.ar/download/paper/paper_01795376_v11_n1_p121_Heintz.pdf |
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01795376_v11_n1_p121_Heintz |
Referencias:
- Bochnak, J., Coste, M., Roy, M.-F., (1987) Géométrie algébrique réelle, , Ergebnisse der Mathematik und ihrer Genzgebiete, 3 Folge, Band 12, Springer-Verlag, Berlin
- [Ca1] Canny, J.: Some algebraic and geometric computations in PSPACE. Proc. 20th Ann. ACM Symp. on Theory of Computing, 1988, pp. 460–467; Canny, J., (1989) The Complexity of Robot Motion Planning, , MIT Press, Cambridge, MA
- Canny, J., Grigor'ev, Vorobjov, N.N., Jr., Finding connected components of a semialgebraic set in subexponential time (1992) AAECC J., 2 (4), pp. 217-238
- Collins, G., Quantifier elimination for real closed fields by cylindric algebraic decomposition (1975) Proc. Second GI Conf. on Automata Theory and Formal Languages, pp. 134-183. , Lecture Notes in Computer Science, Vol. 33, Springer-Verlag, Berlin
- von zer Gathen, J., Parallel arthmetic computations: a survey (1986) Proc. 13th Conf. Symp. MFCS, pp. 93-112. , Lecture Notes in Computer Science, Vol. 233, Springer-Verlag, Berlin
- Grigor'ev, D., Complexity of deciding Tarski algebra (1988) Journal of Symbolic Computation, 5, pp. 65-108
- Grigor'ev, Heintz, J., Roy, M.-F., Solernó, P., Vorobjov, N.N., Jr., Comptage des composantes connexes d'un ensemble semi-algébrique en temps simplement exponentiel (1990) C. R. Acad. Sci. Paris Sér. I, 312, pp. 879-882
- [GR] Gournay, L., Risler, J.-J.: Construction of roadmaps in semi-algebraic sets. J. Appl. Algebra Engrg. Comm. Comput. (to appear); Grigor'ev, D., Vorobjov, N.N., Jr., Solving systems of polynomial inequalities in subexponential time (1988) Journal of Symbolic Computation, 5, pp. 37-64
- [GV2] Grigor'ev, D., Vorobjov, N. N. (Jr.): Counting connected components of a semialgebraic set in subexponential time. Comput. Complexity (to appear); Heintz, J., Roy, M.-F., Solernó, P., On the complexity of semialgebraic sets (1989) Proc. Information Processing (IFIP '89), San Francisco, 1989, pp. 293-298. , G. X., Ritter, North-Holland, Amsterdam
- Heintz, J., Roy, M.-F., Solernó, P., Sur la complexité du principe de Tarski-Seidenberg (1990) Bull. Soc. Math. France, 118, pp. 101-126
- Heintz, J., Roy, M.-F., Solernó, P., Single exponential path finding in semi-algebraic sets. Part I: The case of a regular bounded hypersurface (1991) Discrete and Applied Mathematics, Proc. 8th Internat. Conf. on Applied Algebra, Algebraic Algorithms on Error Correctina, Codes AAECC-8, Tokyo, 1990, pp. 180-186. , S., Sakata, Lecture Notes on Computer Science, Vol. 508, Springer-Verlag, Berlin
- [HRS4] Heintz, J., Roy, M.-F., Solernó, P.: Single exponential path finding in semialgebraic sets. Part II: The general case. Proc. Symp. in Honour of S. Abhyankar (1990) (to appear); Heintz, J., Roy, M.-F., Solernó, P., Description des composantes connexes d'un ensemble semi-algébrique en temps simplement exponential (1991) C. R. Acad. Sci. Paris Sér. 1, 313, pp. 167-170
- Mehlhorn, K., (1984) Data Structures and Algorithms, , EATCS Monographs on Theoretical Computer Science, Vol. 2, Springer-Verlag, Berlin
- Renegar, J., On the computational complexity and geometry of the first order theory of the reals, I (1992) Journal of Symbolic Computation, 13, pp. 255-300
- Renegar, J., On the computational complexity and geometry of the first order theory of the reals, II (1992) Journal of Symbolic Computation, 13, pp. 301-328
- Renegar, J., On the computational complexity and geometry of the first order theory of the reals, III (1992) Journal of Symbolic Computation, 13, pp. 329-352
- Schwartz, J., Sharir, M., On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds (1983) Adv. in Appl. Math., 4, pp. 298-351
- Wüthrich, H., Ein Entscheidungsverfahren für die Theorie der reell-abgeschlos-senen Körper (1976) Komplexität von Entscheidungsproblemen, pp. 138-162. , E., Specker, V., Strassen, Lectures Notes in Computer Science, Vol. 43, Springer-Verlag, Berlin
Citas:
---------- APA ----------
Heintz, J., Roy, M.-F. & Solernó, P.
(1994)
. Description of the connected components of a semialgebraic set in single exponential time. Discrete & Computational Geometry, 11(1), 121-140.
http://dx.doi.org/10.1007/BF02573999---------- CHICAGO ----------
Heintz, J., Roy, M.-F., Solernó, P.
"Description of the connected components of a semialgebraic set in single exponential time"
. Discrete & Computational Geometry 11, no. 1
(1994) : 121-140.
http://dx.doi.org/10.1007/BF02573999---------- MLA ----------
Heintz, J., Roy, M.-F., Solernó, P.
"Description of the connected components of a semialgebraic set in single exponential time"
. Discrete & Computational Geometry, vol. 11, no. 1, 1994, pp. 121-140.
http://dx.doi.org/10.1007/BF02573999---------- VANCOUVER ----------
Heintz, J., Roy, M.-F., Solernó, P. Description of the connected components of a semialgebraic set in single exponential time. Discrete Comput Geom. 1994;11(1):121-140.
http://dx.doi.org/10.1007/BF02573999