### 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 |

### Fingerprint

### Keywords

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

### Cite this

}

**Homotopic C-oriented routing with few links and thick edges.** / Speckmann, B.; Verbeek, K.A.B.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Homotopic C-oriented routing with few links and thick edges

AU - Speckmann, B.

AU - Verbeek, K.A.B.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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κ+kinlogn+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.

AB - 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κ+kinlogn+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.

KW - C-oriented

KW - Homotopic

KW - Minimum-link

KW - Routing

KW - Thick paths

UR - http://www.scopus.com/inward/record.url?scp=85031668733&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2017.10.005

DO - 10.1016/j.comgeo.2017.10.005

M3 - Article

AN - SCOPUS:85031668733

VL - 67

SP - 11

EP - 28

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

ER -