Homotopic Oriented RoutingVerbeek, Kevin (2013) Homotopic Oriented Routing. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 272278(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractWe study the problem of finding noncrossing minimumlink C oriented paths that are homotopic to a set of input paths in an environment with C oriented obstacles. We introduce a special type of C oriented paths—smooth paths—and present a 2approximation algorithm that runs in O(n^2 (n + log_κ) + k in logn) time, where n is the total number of paths and obstacle vertices, k in is the total number of links in the input, and κ=C . The algorithm also computes an O(κ)approximation for general C oriented paths. As a related result we show that, given a set of C oriented paths with L links in total, noncrossing C oriented paths homotopic to the input paths can require a total of Ω(L logκ) links.
Actions (login required)
