## Abstract

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(n^{3}logκ+k_{in}logn+k_{out}) time, where n is the total number of paths and obstacle vertices, k_{in} and k_{out} 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.

Original language | English |
---|---|

Pages (from-to) | 11-28 |

Number of pages | 18 |

Journal | Computational Geometry |

Volume | 67 |

DOIs | |

Publication status | Published - 1 Jan 2018 |

## Keywords

- C-oriented
- Homotopic
- Minimum-link
- Routing
- Thick paths