Approximate Shortest Homotopic Paths in Weighted Regions

Siu-Wing Cheng, Jiongxin Jin, Antoine E. Vigneron, Yajun Wang

Research output: Chapter in Book/Report/Conference proceedingChapter

2 Scopus citations

Abstract

Let P be a path between two points s and t in a polygonal subdivision T with obstacles and weighted regions. Given a relative error tolerance ε ∈(0,1), we present the first algorithm to compute a path between s and t that can be deformed to P without passing over any obstacle and the path cost is within a factor 1 + ε of the optimum. The running time is O(h 3/ε2 kn polylog(k, n, 1/ε)), where k is the number of segments in P and h and n are the numbers of obstacles and vertices in T, respectively. The constant in the running time of our algorithm depends on some geometric parameters and the ratio of the maximum region weight to the minimum region weight. © 2010 Springer-Verlag.
Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science
PublisherSpringer Nature
Pages109-120
Number of pages12
ISBN (Print)9783642175138
DOIs
StatePublished - 2010
Externally publishedYes

Fingerprint Dive into the research topics of 'Approximate Shortest Homotopic Paths in Weighted Regions'. Together they form a unique fingerprint.

Cite this