Advanced

A fast algorithm for approximating the detour of a polygonal chain

Ebbers-Baumann, A; Klein, R; Langetepe, E and Lingas, Andrzej LU (2004) In Computational Geometry 27(2). p.123-134
Abstract
Let C be a simple(1) polygonal chain of n edges in the plane, and let p and q be two arbitrary points on C. The detour of C on (p, q) is defined to be the length of the subchain of C that connects p with q, divided by the Euclidean distance between p and q. Given an epsilon >0, we compute in time O((1)/(epsilon) n log n) a pair of points on which the chain makes a detour at least 1/(1 + epsilon) times the maximum detour. (C) 2003 Elsevier B.V. All rights reserved.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
maximum detour, dilation, approximation, polygonal chains
in
Computational Geometry
volume
27
issue
2
pages
123 - 134
publisher
Elsevier
external identifiers
  • wos:000188548900002
  • scopus:84867956821
ISSN
0925-7721
DOI
10.1016/S0925-7721(03)00046-4
project
VR 2002-4049
language
English
LU publication?
yes
id
d36ec313-7f70-428e-8475-000fdb850712 (old id 288822)
date added to LUP
2007-08-02 12:31:44
date last changed
2017-01-01 06:54:17
@article{d36ec313-7f70-428e-8475-000fdb850712,
  abstract     = {Let C be a simple(1) polygonal chain of n edges in the plane, and let p and q be two arbitrary points on C. The detour of C on (p, q) is defined to be the length of the subchain of C that connects p with q, divided by the Euclidean distance between p and q. Given an epsilon >0, we compute in time O((1)/(epsilon) n log n) a pair of points on which the chain makes a detour at least 1/(1 + epsilon) times the maximum detour. (C) 2003 Elsevier B.V. All rights reserved.},
  author       = {Ebbers-Baumann, A and Klein, R and Langetepe, E and Lingas, Andrzej},
  issn         = {0925-7721},
  keyword      = {maximum detour,dilation,approximation,polygonal chains},
  language     = {eng},
  number       = {2},
  pages        = {123--134},
  publisher    = {Elsevier},
  series       = {Computational Geometry},
  title        = {A fast algorithm for approximating the detour of a polygonal chain},
  url          = {http://dx.doi.org/10.1016/S0925-7721(03)00046-4},
  volume       = {27},
  year         = {2004},
}