A fast algorithm for approximating the detour of a polygonal chain
(2004) In Computational Geometry 27(2). p.123134 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:
http://lup.lub.lu.se/record/288822
 author
 EbbersBaumann, A; Klein, R; Langetepe, E and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2004
 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
 09257721
 DOI
 10.1016/S09257721(03)000464
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 d36ec3137f70428e8475000fdb850712 (old id 288822)
 date added to LUP
 20070802 12:31:44
 date last changed
 20180107 08:59:21
@article{d36ec3137f70428e8475000fdb850712, 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 = {EbbersBaumann, A and Klein, R and Langetepe, E and Lingas, Andrzej}, issn = {09257721}, keyword = {maximum detour,dilation,approximation,polygonal chains}, language = {eng}, number = {2}, pages = {123134}, publisher = {Elsevier}, series = {Computational Geometry}, title = {A fast algorithm for approximating the detour of a polygonal chain}, url = {http://dx.doi.org/10.1016/S09257721(03)000464}, volume = {27}, year = {2004}, }