Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Approximate Shortest Homotopic Paths in Weighted Regions
verfasst von : Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron, Yajun Wang
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
P
be a path between two points
s
and
t
in a polygonal subdivision
$\mathcal 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(\frac{h^3}{\varepsilon^2}kn\,\mathrm{polylog}(k,n,\frac{1}{\varepsilon}))$
, where
k
is the number of segments in
P
and
h
and
n
are the numbers of obstacles and vertices in
$\mathcal 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.