Homotopic rectilinear routing with few links and thick edges

Research output: Contribution to conferenceAbstractAcademic

90 Downloads (Pure)


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 languageEnglish
Publication statusPublished - 2009
Event25th European Workshop on Computational Geometry (EuroCG 2009) - Brussels, Belgium
Duration: 16 Mar 200918 Mar 2009
Conference number: 25


Workshop25th European Workshop on Computational Geometry (EuroCG 2009)
Abbreviated titleEuroCG


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

Cite this