Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space

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

doi:10.1142/S0218195912600035

Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space

Christian Wulff-Nilsen, Ansgar Grüne, Rolf Klein, Elmar Langetepe, D. T. Lee, Tien Ching Lin^*, Sheung Hung Poon, Teng Kai Yu

^*Corresponding author af dette arbejde

Datalogisk Institut

Abstract

The stretch factor and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and the metric space, respectively. In this paper we show that computing the stretch factor of a rectilinear path in L ₁ plane has a lower bound of Ω(n log n) in the algebraic computation tree model and describe a worst-case O(σn log ² n) time algorithm for computing the stretch factor or maximum detour of a path embedded in the plane with a weighted fixed orientation metric defined by σ < 2 vectors and a worst-case O(n log ^d n) time algorithm to d < 3 dimensions in L ₁-metric. We generalize the algorithms to compute the stretch factor or maximum detour of trees and cycles in O(σn log ^d+1 n) time. We also obtain an optimal O(n) time algorithm for computing the maximum detour of a monotone rectilinear path in L ₁ plane.

Originalsprog	Engelsk
Tidsskrift	International Journal of Computational Geometry and Applications
Vol/bind	22
Udgave nummer	1
Sider (fra-til)	45-60
Antal sider	16
ISSN	0218-1959
DOI	https://doi.org/10.1142/S0218195912600035
Status	Udgivet - 2012

Adgang til dokumentet

10.1142/S0218195912600035

Andre filer og links

Link to publication in Scopus

Citationsformater

@article{7f059907519f48b39d716e2d50d65f91,

title = "Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space",

abstract = "The stretch factor and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and the metric space, respectively. In this paper we show that computing the stretch factor of a rectilinear path in L 1 plane has a lower bound of Ω(n log n) in the algebraic computation tree model and describe a worst-case O(σn log 2 n) time algorithm for computing the stretch factor or maximum detour of a path embedded in the plane with a weighted fixed orientation metric defined by σ < 2 vectors and a worst-case O(n log d n) time algorithm to d < 3 dimensions in L 1-metric. We generalize the algorithms to compute the stretch factor or maximum detour of trees and cycles in O(σn log d+1 n) time. We also obtain an optimal O(n) time algorithm for computing the maximum detour of a monotone rectilinear path in L 1 plane.",

keywords = "cycle, dilation, L metric, maximum detour, Rectilinear path, spanning ratio, stretch factor, tree, weighted fixed orientation metric",

author = "Christian Wulff-Nilsen and Ansgar Gr{\"u}ne and Rolf Klein and Elmar Langetepe and Lee, {D. T.} and Lin, {Tien Ching} and Poon, {Sheung Hung} and Yu, {Teng Kai}",

year = "2012",

doi = "10.1142/S0218195912600035",

language = "English",

volume = "22",

pages = "45--60",

journal = "International Journal of Computational Geometry and Applications",

issn = "0218-1959",

publisher = "World Scientific Publishing Co. Pte. Ltd.",

number = "1",

}

TY - JOUR

T1 - Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space

AU - Wulff-Nilsen, Christian

AU - Grüne, Ansgar

AU - Klein, Rolf

AU - Langetepe, Elmar

AU - Lee, D. T.

AU - Lin, Tien Ching

AU - Poon, Sheung Hung

AU - Yu, Teng Kai

PY - 2012

Y1 - 2012

N2 - The stretch factor and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and the metric space, respectively. In this paper we show that computing the stretch factor of a rectilinear path in L 1 plane has a lower bound of Ω(n log n) in the algebraic computation tree model and describe a worst-case O(σn log 2 n) time algorithm for computing the stretch factor or maximum detour of a path embedded in the plane with a weighted fixed orientation metric defined by σ < 2 vectors and a worst-case O(n log d n) time algorithm to d < 3 dimensions in L 1-metric. We generalize the algorithms to compute the stretch factor or maximum detour of trees and cycles in O(σn log d+1 n) time. We also obtain an optimal O(n) time algorithm for computing the maximum detour of a monotone rectilinear path in L 1 plane.

AB - The stretch factor and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and the metric space, respectively. In this paper we show that computing the stretch factor of a rectilinear path in L 1 plane has a lower bound of Ω(n log n) in the algebraic computation tree model and describe a worst-case O(σn log 2 n) time algorithm for computing the stretch factor or maximum detour of a path embedded in the plane with a weighted fixed orientation metric defined by σ < 2 vectors and a worst-case O(n log d n) time algorithm to d < 3 dimensions in L 1-metric. We generalize the algorithms to compute the stretch factor or maximum detour of trees and cycles in O(σn log d+1 n) time. We also obtain an optimal O(n) time algorithm for computing the maximum detour of a monotone rectilinear path in L 1 plane.

KW - cycle

KW - dilation

KW - L metric

KW - maximum detour

KW - Rectilinear path

KW - spanning ratio

KW - stretch factor

KW - tree

KW - weighted fixed orientation metric

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

U2 - 10.1142/S0218195912600035

DO - 10.1142/S0218195912600035

M3 - Journal article

AN - SCOPUS:84866291833

SN - 0218-1959

VL - 22

SP - 45

EP - 60

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 1

ER -

Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space

Abstract

Adgang til dokumentet

Andre filer og links

Fingeraftryk

Citationsformater