Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
; ; and
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
2016-04-01 16:03:16
date last changed
2022-04-15 01:44:16
@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}},
  keywords     = {{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}},
  doi          = {{10.1016/S0925-7721(03)00046-4}},
  volume       = {{27}},
  year         = {{2004}},
}