The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

A fast algorithm for approximating the detour of a polygonal chain

På svenska

Author

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.

Department/s

  • Computer Science

Publishing year

2004

Language

English

Pages

123-134

Publication/Series

Computational Geometry

Volume

27

Issue

2

Document type

Journal article

Publisher

Elsevier

Topic

  • Computer Science

Keywords

  • maximum detour
  • dilation
  • approximation
  • polygonal chains

Status

Published

Project

  • VR 2002-4049

ISBN/ISSN/Other

  • ISSN: 0925-7721