Homotopic rectilinear routing with few links and thick edges

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationLATIN 2010: Theoretical Informatics (Proceedings 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010)
EditorsA. López-Ortiz
Place of PublicationBerlin
PublisherSpringer
Pages468-479
ISBN (Print)978-3-642-12199-9
DOIs
Publication statusPublished - 2010

Publication series

NameLecture Notes in Computer Science
Volume6034
ISSN (Print)0302-9743

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

Cite this