Abstract
We study the problem of finding non-crossing thick minimum-link rectilinear paths homotopic to a set of input paths in an environment with rectangular obstacles. This problem occurs in the context of map schematization under geometric embedding restrictions, for example, when schematizing a highway network for use as a thematic layer. We present a 2-approximation algorithm that runs in O(n3 +kin log n + kout) time, where n is the total number of input paths and obstacles and kin and kout are the total complexities of the input and output paths, respectively. Our algorithm not only approximates the minimum number of links, but also minimizes the total length of the paths. An approximation factor of 2 is optimal when using smallest paths as lower bound.
| Original language | English |
|---|---|
| Pages | 243-246 |
| Publication status | Published - 2009 |
| Event | 25th European Workshop on Computational Geometry (EuroCG 2009) - Brussels, Belgium Duration: 16 Mar 2009 → 18 Mar 2009 Conference number: 25 |
Workshop
| Workshop | 25th European Workshop on Computational Geometry (EuroCG 2009) |
|---|---|
| Abbreviated title | EuroCG |
| Country/Territory | Belgium |
| City | Brussels |
| Period | 16/03/09 → 18/03/09 |