Homotopic  -Oriented Routing

Verbeek, Kevin (2013) Homotopic  -Oriented Routing. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 272-278(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

Full text not available from this repository.


We study the problem of finding non-crossing minimum-link 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 2-approximation 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, non-crossing C -oriented paths homotopic to the input paths can require a total of Ω(L logκ) links.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-36763-2_24
Classifications: P Styles > P.600 Poly-line
P Styles > P.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1316

Actions (login required)

View Item View Item