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

Fingerprint

Approximation algorithms
Routing
Path
Approximation Algorithms
Minimise
NP-hard Problems
Optimization Problem

Keywords

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

Cite this

@article{b6e7f13857a94f20a450a8edf637826d,
title = "Homotopic C-oriented routing with few links and thick edges",
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.",
keywords = "C-oriented, Homotopic, Minimum-link, Routing, Thick paths",
author = "B. Speckmann and K.A.B. Verbeek",
year = "2018",
month = "1",
day = "1",
doi = "10.1016/j.comgeo.2017.10.005",
language = "English",
volume = "67",
pages = "11--28",
journal = "Computational Geometry",
issn = "0925-7721",
publisher = "Elsevier",

}

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

In: Computational Geometry, Vol. 67, 01.01.2018, p. 11-28.

Research output: Contribution to journalArticleAcademicpeer-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⁡κ+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.

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⁡κ+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.

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 -