Computing homotopic shortest paths efficiently Export

@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}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.comgeo.2006.03.003}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6TYS-4JYTRTW-1/2/1031e223a5a2442f71cd32b1e6fbd23c}, doi = {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 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. IS - 3 JF - Computational Geometry EP - 172 TI - Computing homotopic shortest paths efficiently VL - 35 SP - 162 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 -