Geodesic
Construction of a shortest path around semi-algebraic obstacles in the plane
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 5, Tome 192 (1991), pp. 163-173 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The authors describe an algorithm that in polynomial time reduces the problem of finding a shortest path (between 2 points) not intersecting semi-algebraic obstacles in the plane, to the problem of finding a least cost path in a graph which vertex cests are integrals of positive algebraic functions (without singularities). As a consequence one gets an algorithm which in time polynomial in the leagth of input and $1/\varepsilon$, constructs an $\varepsilon$-approximation to a shortest path. Related problems and results are briefly discussed. 
@article{ZNSL_1991_192_a7,
     author = {T. Krick and A. O. Slissenko and P. Solern\'o and J. Heintz},
     title = {Construction of a shortest path around semi-algebraic obstacles in the plane},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {163--173},
     year = {1991},
     volume = {192},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_1991_192_a7/}
}
TY  - JOUR
AU  - T. Krick
AU  - A. O. Slissenko
AU  - P. Solernó
AU  - J. Heintz
TI  - Construction of a shortest path around semi-algebraic obstacles in the plane
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 1991
SP  - 163
EP  - 173
VL  - 192
UR  - http://geodesic.mathdoc.fr/item/ZNSL_1991_192_a7/
LA  - ru
ID  - ZNSL_1991_192_a7
ER  - 
%0 Journal Article
%A T. Krick
%A A. O. Slissenko
%A P. Solernó
%A J. Heintz
%T Construction of a shortest path around semi-algebraic obstacles in the plane
%J Zapiski Nauchnykh Seminarov POMI
%D 1991
%P 163-173
%V 192
%U http://geodesic.mathdoc.fr/item/ZNSL_1991_192_a7/
%G ru
%F ZNSL_1991_192_a7
T. Krick; A. O. Slissenko; P. Solernó; J. Heintz. Construction of a shortest path around semi-algebraic obstacles in the plane. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 5, Tome 192 (1991), pp. 163-173. http://geodesic.mathdoc.fr/item/ZNSL_1991_192_a7/