Spanning ratio and maximum detour of rectilinear paths in the L1 plane

Ansgar Grüne; Tien Ching Lin; Teng Kai Yu; Rolf Klein; Elmar Langetepe; D. T. Lee; Sheung Hung Poon

doi:10.1007/978-3-642-17514-5_11

Spanning ratio and maximum detour of rectilinear paths in the L₁ plane

Ansgar Grüne, Tien Ching Lin, Teng Kai Yu, Rolf Klein, Elmar Langetepe, D. T. Lee, Sheung Hung Poon

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

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 L₁ space has a lower bound of Ω(n logn) in the algebraic computation tree model and describe a deterministic O(n log² n) time algorithm. On the other hand, we give a deterministic O(n log² n) time algorithm for computing the maximum detour of a rectilinear path P in L₁ space and obtain an O(n) time algorithm when P is a monotone rectilinear path.

Original language	English
Title of host publication	Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings
Pages	121-131
Number of pages	11
Edition	PART 2
DOIs	https://doi.org/10.1007/978-3-642-17514-5_11
Publication status	Published - 2010
Externally published	Yes
Event	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of Duration: 15 Dec 2010 → 17 Dec 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 2
Volume	6507 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
Country/Territory	Korea, Republic of
City	Jeju Island
Period	15/12/10 → 17/12/10

Keywords

L metric
Manhattan plane
dilation
maximum detour
rectilinear path
spanning ratio

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-17514-5_11

Cite this

Grüne, A., Lin, T. C., Yu, T. K., Klein, R., Langetepe, E., Lee, D. T., & Poon, S. H. (2010). Spanning ratio and maximum detour of rectilinear paths in the L₁ plane. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings (PART 2 ed., pp. 121-131). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6507 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-17514-5_11

Grüne, Ansgar ; Lin, Tien Ching ; Yu, Teng Kai et al. / Spanning ratio and maximum detour of rectilinear paths in the L₁ plane. Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2. ed. 2010. pp. 121-131 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@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",

}

Grüne, A, Lin, TC, Yu, TK, Klein, R, Langetepe, E, Lee, DT & Poon, SH 2010, Spanning ratio and maximum detour of rectilinear paths in the L₁ plane. in Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 6507 LNCS, pp. 121-131, 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010, Jeju Island, Korea, Republic of, 15/12/10. https://doi.org/10.1007/978-3-642-17514-5_11

Spanning ratio and maximum detour of rectilinear paths in the L₁ plane. / Grüne, Ansgar; Lin, Tien Ching; Yu, Teng Kai et al.
Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2. ed. 2010. p. 121-131 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6507 LNCS, No. PART 2).

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Spanning ratio and maximum detour of rectilinear paths in the L1 plane

AU - Grüne, Ansgar

AU - Lin, Tien Ching

AU - Yu, Teng Kai

AU - Klein, Rolf

AU - Langetepe, Elmar

AU - Lee, D. T.

AU - Poon, Sheung Hung

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - L metric

KW - Manhattan plane

KW - dilation

KW - maximum detour

KW - rectilinear path

KW - spanning ratio

UR - http://www.scopus.com/inward/record.url?scp=78650895872&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17514-5_11

DO - 10.1007/978-3-642-17514-5_11

M3 - Conference contribution

AN - SCOPUS:78650895872

SN - 3642175163

SN - 9783642175169

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 121

EP - 131

BT - Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings

T2 - 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010

Y2 - 15 December 2010 through 17 December 2010

ER -

Grüne A, Lin TC, Yu TK, Klein R, Langetepe E, Lee DT et al. Spanning ratio and maximum detour of rectilinear paths in the L₁ plane. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2 ed. 2010. p. 121-131. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). doi: 10.1007/978-3-642-17514-5_11