We study the NP-hard problem of finding non-crossing thick minimum-link rectilinear paths which are homotopic to a set of input paths in an environment with rectangular obstacles. We present a 2-approximation that runs in O(n 3 + k_in log n+ k_out) time, where n is the total number of input paths and obstacles and k in and k out are the total complexities of the input and output paths. Our algorithm not only approximates the minimum number of links, but also simultaneously minimizes the total length of the paths. We also show that an approximation factor of 2 is optimal when using smallest paths as lower bound.
|Title of host publication||LATIN 2010: Theoretical Informatics (Proceedings 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010)|
|Place of Publication||Berlin|
|Publication status||Published - 2010|
|Name||Lecture Notes in Computer Science|