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

Research output: Chapter in Book/Conference proceedingConference contributionpeer-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 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.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings
Pages121-131
Number of pages11
EditionPART 2
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of
Duration: 15 Dec 201017 Dec 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume6507 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
Country/TerritoryKorea, Republic of
CityJeju Island
Period15/12/1017/12/10

Keywords

  • L metric
  • Manhattan plane
  • dilation
  • maximum detour
  • rectilinear path
  • spanning ratio

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Spanning ratio and maximum detour of rectilinear paths in the L1 plane'. Together they form a unique fingerprint.

Cite this