Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface

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 para...

Descripción completa

Detalles Bibliográficos
Publicado: 1991
Materias:
Algebra
Boolean combinations
Connected component
Hypersurface
Path finding
Polynomial equation
Polynomial inequalities
Semi-algebraic sets
Time bound
Polynomials
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v508LNCS_n_p180_Heintz
http://hdl.handle.net/20.500.12110/paper_03029743_v508LNCS_n_p180_Heintz
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_03029743_v508LNCS_n_p180_Heintz
record_format dspace
spelling paper:paper_03029743_v508LNCS_n_p180_Heintz2023-06-08T15:28:27Z Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface Algebra Boolean combinations Connected component Hypersurface Path finding Polynomial equation Polynomial inequalities Semi-algebraic sets Time bound Polynomials 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. 1991 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v508LNCS_n_p180_Heintz http://hdl.handle.net/20.500.12110/paper_03029743_v508LNCS_n_p180_Heintz
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Algebra
Boolean combinations
Connected component
Hypersurface
Path finding
Polynomial equation
Polynomial inequalities
Semi-algebraic sets
Time bound
Polynomials
spellingShingle Algebra
Boolean combinations
Connected component
Hypersurface
Path finding
Polynomial equation
Polynomial inequalities
Semi-algebraic sets
Time bound
Polynomials
Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface
topic_facet Algebra
Boolean combinations
Connected component
Hypersurface
Path finding
Polynomial equation
Polynomial inequalities
Semi-algebraic sets
Time bound
Polynomials
description 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.
title Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface
title_short Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface
title_full Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface
title_fullStr Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface
title_full_unstemmed Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface
title_sort single exponential path finding in semialgebraic sets part i: the case of a regular bounded hypersurface
publishDate 1991
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v508LNCS_n_p180_Heintz
http://hdl.handle.net/20.500.12110/paper_03029743_v508LNCS_n_p180_Heintz
_version_ 1768541609662611456

Ejemplares similares