Geodesic
Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Fourth International Workshop on Algorithms and Computation (WALCOM 2010) , Tome 15 (2011) no. 5, pp. 569-586.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Constant-work-space algorithms model computation when space is at a premium: the input is given as a read-only array that allows random access to its entries, and the algorithm may use constantly many additional registers of O(logn) bits each, where n denotes the input size. We present such algorithms for two restricted variants of the shortest path problem. First, we describe how to report a simple path between two arbitrary nodes in a given tree. Using a technique called "computing instead of storing", we obtain a naive algorithm that needs quadratic time and a constant number of additional registers. We then show how to improve the running time to linear by applying a technique named "simulated parallelization". Second, we show how to compute a shortest geodesic path between two points in a simple polygon in quadratic time and with constant work-space.
DOI : 10.7155/jgaa.00240
Keywords: computational geometry, constant work-space, shortest path, simple polygon 
@article{JGAA_2011_15_5_a1,
     author = {Tetsuo Asano and Wolfgang Mulzer and Yajun Wang},
     title = {Constant-Work-Space {Algorithms} for {Shortest} {Paths} in {Trees} and {Simple} {Polygons}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {569--586},
     publisher = {mathdoc},
     volume = {15},
     number = {5},
     year = {2011},
     doi = {10.7155/jgaa.00240},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00240/}
}
TY  - JOUR
AU  - Tetsuo Asano
AU  - Wolfgang Mulzer
AU  - Yajun Wang
TI  - Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons
JO  - Journal of Graph Algorithms and Applications
PY  - 2011
SP  - 569
EP  - 586
VL  - 15
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00240/
DO  - 10.7155/jgaa.00240
LA  - en
ID  - JGAA_2011_15_5_a1
ER  - 
%0 Journal Article
%A Tetsuo Asano
%A Wolfgang Mulzer
%A Yajun Wang
%T Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons
%J Journal of Graph Algorithms and Applications
%D 2011
%P 569-586
%V 15
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00240/
%R 10.7155/jgaa.00240
%G en
%F JGAA_2011_15_5_a1
Tetsuo Asano; Wolfgang Mulzer; Yajun Wang. Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Fourth International Workshop on Algorithms and Computation (WALCOM 2010)
					, Tome 15 (2011) no. 5, pp. 569-586. doi : 10.7155/jgaa.00240. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00240/

Cité par Sources :