Homotopic C-oriented routing with few links and thick edges

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

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(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.

Original languageEnglish
Pages (from-to)11-28
Number of pages18
JournalComputational Geometry
Volume67
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

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

Fingerprint Dive into the research topics of 'Homotopic C-oriented routing with few links and thick edges'. Together they form a unique fingerprint.

Cite this