@inproceedings{6d70ad0ccf9c496697e7bb61ba32ceff,
title = "Spanning ratio and maximum detour of rectilinear paths in the L1 plane",
abstract = "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 L1 space has a lower bound of Ω(n logn) in the algebraic computation tree model and describe a deterministic O(n log2 n) time algorithm. On the other hand, we give a deterministic O(n log2 n) time algorithm for computing the maximum detour of a rectilinear path P in L1 space and obtain an O(n) time algorithm when P is a monotone rectilinear path.",
keywords = "L metric, Manhattan plane, dilation, maximum detour, rectilinear path, spanning ratio",
author = "Ansgar Gr{\"u}ne and Lin, {Tien Ching} and Yu, {Teng Kai} and Rolf Klein and Elmar Langetepe and Lee, {D. T.} and Poon, {Sheung Hung}",
year = "2010",
doi = "10.1007/978-3-642-17514-5_11",
language = "English",
isbn = "3642175163",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
number = "PART 2",
pages = "121--131",
booktitle = "Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings",
edition = "PART 2",
note = "21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 ; Conference date: 15-12-2010 Through 17-12-2010",
}