Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6868543 | Computational Geometry | 2018 | 24 Pages |
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
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Bettina Speckmann, Kevin Verbeek,