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

Guardado en:
Detalles Bibliográficos
Autores principales: Heintz, J., Roy, M.-F., Solero, P., Sakata S.
Formato: SER
Materias:
Algebra
Boolean combinations
Connected component
Hypersurface
Path finding
Polynomial equation
Polynomial inequalities
Semi-algebraic sets
Time bound
Polynomials
Acceso en línea: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 todo:paper_03029743_v508LNCS_n_p180_Heintz
record_format dspace
spelling todo:paper_03029743_v508LNCS_n_p180_Heintz2023-10-03T15:19:02Z Single exponential path finding in semialgebraic sets part I: The case of a regular bounded hypersurface Heintz, J. Roy, M.-F. Solero, P. Sakata S. 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. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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
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
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.
format SER
author Heintz, J.
Roy, M.-F.
Solero, P.
Sakata S.
author_facet Heintz, J.
Roy, M.-F.
Solero, P.
Sakata S.
author_sort Heintz, J.
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
url http://hdl.handle.net/20.500.12110/paper_03029743_v508LNCS_n_p180_Heintz
work_keys_str_mv AT heintzj singleexponentialpathfindinginsemialgebraicsetspartithecaseofaregularboundedhypersurface
AT roymf singleexponentialpathfindinginsemialgebraicsetspartithecaseofaregularboundedhypersurface
AT solerop singleexponentialpathfindinginsemialgebraicsetspartithecaseofaregularboundedhypersurface
AT sakatas singleexponentialpathfindinginsemialgebraicsetspartithecaseofaregularboundedhypersurface
_version_ 1807315270732087296

Ejemplares similares