Computing homotopic shortest paths efficiently

@article{citeulike:884382, abstract = {We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection [Pi] of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time , and the randomized algorithm runs in expected time O(kout+kinlogn+n(logn)1+[epsilon]). Here kin is the number of edges in all the paths of [Pi], and kout is the number of edges in the output paths.}, author = {Efrat, Alon and Kobourov, Stephen G. and Lubiw, Anna }, citeulike-article-id = {884382}, doi = {http://dx.doi.org/10.1016/j.comgeo.2006.03.003}, journal = {Computational Geometry}, keywords = {geometry, shortestpath}, month = {October}, number = {3}, pages = {162--172}, posted-at = {2006-10-05 06:27:18}, priority = {2}, title = {Computing homotopic shortest paths efficiently}, url = {http://dx.doi.org/10.1016/j.comgeo.2006.03.003}, volume = {35}, year = {2006} }

TY - JOUR ID - citeulike:884382 L3 - citeulike-article-id:884382 TI - Computing homotopic shortest paths efficiently JF - Computational Geometry VL - 35 IS - 3 SP - 162 EP - 172 N2 - We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection [Pi] of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time , and the randomized algorithm runs in expected time O(kout+kinlogn+n(logn)1+[epsilon]). Here kin is the number of edges in all the paths of [Pi], and kout is the number of edges in the output paths. KW - geometry KW - shortestpath AU - Efrat, Alon AU - Kobourov, Stephen AU - Lubiw, Anna PY - 2006/10// UR - http://dx.doi.org/10.1016/j.comgeo.2006.03.003 ER -