A fast algorithm for approximating the detour of a polygonal chain
Författare
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.
Avdelning/ar
- Computer Science
Publiceringsår
2004
Språk
Engelska
Sidor
123-134
Publikation/Tidskrift/Serie
Computational Geometry
Volym
27
Issue
2
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