Homotopic C-oriented routing with few links and thick edges

We study the NP-hard optimization problem of finding non-crossing thick C-oriented paths that are homotopic to a set of input paths in an environment with C-oriented obstacles, with the goal to minimize the total number of links of the paths. We introduce a special type of C-oriented paths-smooth paths-and present a 2-approximation algorithm for smooth paths that runs in O(n3log⁡κ+kinlog⁡n+kout) time, where n is the total number of paths and obstacle vertices, kin and kout are the total complexities of the input and output paths, and κ=|C|. The algorithm also computes an O(κ)-approximation for general C-oriented paths. In particular we give a 2-approximation algorithm for rectilinear paths. Our algorithm not only approximates the minimum number of links, but also simultaneously minimizes the total length of the paths. As a related result we show that, given a set of (possibly crossing) C-oriented paths with a total of L links, non-crossing C-oriented paths homotopic to the input paths can require a total of Ω(Llog⁡κ) links.