A fast algorithm for approximating the detour of a polygonal chain
(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:
https://lup.lub.lu.se/record/288822
- author
- Ebbers-Baumann, 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
- 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}}, }