Oswin Aichholzer, Franz Aurenhammer, Christian Icking, Rolf Klein, Elmar Langetepe, and Günter Rote:

Generalized self-approaching curves

  1. In: "Algorithms and Computation—Ninth Annual International Symposium on Algorithms and Computation. Taejon, Korea, December 1998". Proceedings of ISAAC'98. Editors: Kyung-Yong Chwa and Oscar H. Ibarra. Lecture Notes in Computer Science 1533, Springer-Verlag, 1998, pp. 317–327. doi:10.1007/3-540-49381-6_34
  2. Discrete Applied Mathematics 109 (2001), 3–24. doi:10.1016/S0166-218X(00)00233-X

Abstract

For an angle φ between 0 and 180o, we consider the class of oriented curves which are φ-self-approaching in the following sense: for any point A on the considered curve, the rest of the curve is inside a wedge of angle φ at A. This is a direct generalization of self-approaching curves which are 90o-self-approaching. We prove a tight upper bound on the length of a φ-self-approaching curve in terms of the distance between its endpoints. The upper bound only depends on the angle φ.

This problem arises in the performance analysis of certain on-line navigation strategies. A closely related problem concerns curves with increasing chords.

  PostScript file (gzipped)  pdf file
other papers about this subject
Last update: April 5, 2002.