Navegar

Colección

Datos Estadísticas

Artículo

Heintz, J.; Roy, M.-F.; Solero, P.; Sakata S. "Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface" (1991) 8th International Conference on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC 1990. 508 LNCS:180-196
El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Let V be a bounded semialgebraic hypersurface defined by a regular polynomial equation and let x1, x2 be two points of V. Assume that x1, x2 are given by a boolean combination of polynomial inequalities. We describe an algorithm which decides in single exponential sequential time and polynomial parallel time whether x1 and x2 are contained in the same semialgebraically connected component of V. If they do, the algorithm constructs a continuous semialgebraic path of V connecting x1 and x2. By the way the algorithm constructs a roadmap of V. In particular we obtain that the number of semialgebraically connected components of V is computable within the mentioned time bounds. © Springer-Verlag Berlin Heidelberg 1991.

Registro:

Documento: Artículo
Título:Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface
Autor:Heintz, J.; Roy, M.-F.; Solero, P.; Sakata S.
Filiación:Working Group Noaä Fitchas, Instituto Argentino de Matemática CONICET, Viamonte 1636, Buenos Aires, 1055, Argentina
IRMAR, Université de Rennes I, Refines Cedex, 35042, France
Facultad de Cienclas Exactas y Naturales, Dpto. De Matemática (Univ de Buenos Aires), Ciudad Universitarla, Buenos Aires, 1428, Argentina
Palabras clave:Algebra; Boolean combinations; Connected component; Hypersurface; Path finding; Polynomial equation; Polynomial inequalities; Semi-algebraic sets; Time bound; Polynomials
Año:1991
Volumen:508 LNCS
Página de inicio:180
Página de fin:196
DOI: http://dx.doi.org/10.1007/3-540-54195-0_50
Título revista:8th International Conference on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC 1990
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v508LNCS_n_p180_Heintz

Referencias:

  • Bochnak, J., Coste, M., Roy, M.-F., (1987) Géométrie algébrique réelle, , Springer Verlag
  • Canny, J., Some algebraic and geometric computations in PSPACE (1988) ACM Symptosium on the Theory of Computation, pp. 460-467
  • Canny, J., (1988) The Complexity of Motion Planning, , M.I.T. Thesis 1986, M.I.T. Press
  • Canny, J., A new algebraic method for robot motion planning and real geometry (1987) Proc. 28Th IEEE Symp on Found of Comp. Science (FOCS), pp. 39-48
  • Canny, J., Grigor'ev, D., Vorobjov, N., (1990) Defining Connected Components of a Semialgebraic Set in Subexponential Time, , Manuscript Steklov Mathematical Inst., Leningrad, LOMI
  • Coste, M., Roy, M.-F., Thom’s lemma, the coding of real algebraic numbers and the topology of semialgebraic sets (1988) J. Symbolic Computation, 5, pp. 121-129
  • Fitchas, N., Galligo, A., Morgenstern, J., Algorithmes rapides en séquentiel et en parallèle pour l'élimination des quantificateurs en géométrie élémentaire (1990) Sém. Structures Algébriques Ordonnées, Sélection d'exposés 1984-1987 Vol I. Publ. Univ. Paris, 7 (32), pp. 29-35
  • Von Zur Gathen, J., Parallel arithmetic computations; a survey (1986) Proc. 13Th Conf. MFCS
  • Grigor'ev, D., Complexity of deciding Tarski algebra (1988) J. Symbolic Computation, 5, pp. 65-108
  • Grigor'ev, D., Vorobjov, N., Solving systems of polynomial inequalities in subexponential time (1988) J. Symbolic Computation, 5, pp. 37-64
  • Grigor'ev, D., Vorobjov, N., (1990) Counting Connected Components of a Semialgebraic Set in Subexponential Time, , Manuscript Steklov Mathematica Inst., Leningrad, LOMI
  • Grigor'ev, D., Heintz, J., Roy, M.-F., Solernó, P., Vorobjov, N., Comptage Des Composantes Connexes D'un Ensemble semi-algébrique En Temps Simplement Exponentiel, , To appear in C.R. Acad. Sci. Paris
  • Heintz, J., Roy, M.-F., Solernó, P., On the complexity of semialgebraic sets (1989) Proc. IFIP’89, pp. 293-298
  • Heintz, J., Roy, M.-F., Solernó, P., Complexité du principe de Tarski-Seidenberg (1989) Comptes Rendus De l’Acad. De Sciences Paris, 309, pp. 825-830
  • Heintz, J., Roy, M.-F., Solernó, P., Sur la complexité du principe de Tarski-Seidenberg (1990) Bulletin De La Soc. Math. De France, 118, pp. 101-126
  • Heintz, J., Roy, M.-F., Solernó, P., (1990) Construction De Chemins Dans Un Ensemble semi-algébrique (II), , Preprint
  • Heintz, J., Krick, T., Roy, M.-F., Solernó, P., (1990) Geometric Problems Solvable in Single Exponential Time, , Preprint
  • Renegar, J., (1989) On the Computational Complexity and Geometry of the First Order Theory of the Reals, , Technical Report 856, Cornell Univ
  • Roy, M.-F., Szpirglas, A., (1990) Sign Determination on 0-Dimensional Sets, , To appear in Proc. MEGA’90, Castiglioncello
  • Schwartz, J., Sharir, M., On the piano movers' problem: II General Techniques for calculating topological properties of real algebraic manifolds (1983) Adv. Appl. Math, pp. 298-351
  • Solernó, P., (1989) Complejidad De Conjuntos Semialgebraicos, , Thesis Univ. de Buenos Aires
  • Solernó, P., (1990) Construction De Fonctions De Morse Pour Une Hypersurface régulière En Temps Admissible, , Preprint
  • Trotman, D., (1989) On Canny’s Roadmap Algorithm: Orienteering in Semialgebraic Sets, , Manuscript Univ. Aix-Marseille
  • Valiant, L., Skyum, S., Berkowitz, S., Rackoff, C., Fast parallel computation of polynomials using few processors (1983) SIAM J. Comp, 12, pp. 641-644A4 - Advanced Company Ltd.; Inoue Foundation for Science; International Communications Foundation; Matsushita Electric Industrial Company Ltd.; Mitsubishi Electric Corporation

Citas:

---------- APA ----------
Heintz, J., Roy, M.-F., Solero, P. & Sakata S. (1991) . Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface. 8th International Conference on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC 1990, 508 LNCS, 180-196.
http://dx.doi.org/10.1007/3-540-54195-0_50
---------- CHICAGO ----------
Heintz, J., Roy, M.-F., Solero, P., Sakata S. "Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface" . 8th International Conference on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC 1990 508 LNCS (1991) : 180-196.
http://dx.doi.org/10.1007/3-540-54195-0_50
---------- MLA ----------
Heintz, J., Roy, M.-F., Solero, P., Sakata S. "Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface" . 8th International Conference on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC 1990, vol. 508 LNCS, 1991, pp. 180-196.
http://dx.doi.org/10.1007/3-540-54195-0_50
---------- VANCOUVER ----------
Heintz, J., Roy, M.-F., Solero, P., Sakata S. Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface. Lect. Notes Comput. Sci. 1991;508 LNCS:180-196.
http://dx.doi.org/10.1007/3-540-54195-0_50