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...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | SER |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_03029743_v508LNCS_n_p180_Heintz |
| Aporte de: |
| Sumario: | 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. |
|---|