Advertisement
Published in:
2010 | OriginalPaper | Chapter
Spanning Ratio and Maximum Detour of Rectilinear Paths in the L 1 Plane
Authors : Ansgar Grüne, Tien-Ching Lin, Teng-Kai Yu, Rolf Klein, Elmar Langetepe, D. T. Lee, Sheung-Hung Poon
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The spanning ratio and maximum detour of a graph
G
embedded in a metric space measure how well
G
approximates the minimum complete graph containing
G
and metric space, respectively. In this paper we show that computing the spanning ratio of a rectilinear path
P
in
L
1
space has a lower bound of Ω(
n
log
n
) in the algebraic computation tree model and describe a deterministic
O
(
n
log
2
n
) time algorithm. On the other hand, we give a deterministic
O
(
n
log
2
n
) time algorithm for computing the maximum detour of a rectilinear path
P
in
L
1
space and obtain an
O
(
n
) time algorithm when
P
is a monotone rectilinear path.