A fast algorithm for approximating the detour of a polygonal chain

Summary, in English

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.

• Författare: A Ebbers-Baumann; R Klein; E Langetepe; Andrzej Lingas
• Avdelning/ar: Computer Science
• Publiceringsår: 2004
• Språk: Engelska
• Sidor: 123-134
• Publikation/Tidskrift/Serie: Computational Geometry
• Volym: 27
• Issue: 2
• Länkar: http://dx.doi.org/10.1016/S0925-7721(03)00046-4
• Dokumenttyp: Artikel i tidskrift
• Förlag: Elsevier
• Ämne: Computer Science
• Nyckelord: maximum detour; dilation; approximation; polygonal chains
• Status: Published
• Projekt: VR 2002-4049
• ISBN/ISSN/Övrigt: ISSN: 0925-7721