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

Research output: Contribution to journalJournal articleResearchpeer-review

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.

Original languageEnglish
JournalInternational Journal of Computational Geometry and Applications
Volume22
Issue number1
Pages (from-to)45-60
Number of pages16
ISSN0218-1959
DOIs
Publication statusPublished - 2012

    Research areas

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

ID: 172848699