Abstract
We consider all planar oriented curves that have the following property depending on a fixed angle ϕ. For each point B on the curve, the rest of the curve lies inside a wedge of angle ϕ with apex in B. This property restrains the curve’s meandering, and for ϕ < - π/2 this means that a point running along the curve always gets closer to all points on the remaining part. For all ϕ < π, we provide an upper bound c(ϕ) for the length of such a curve, divided by the distance between its endpoints, and prove this bound to be tight. A main step is in proving that the curve’s length cannot exceed the perimeter of its convex hull, divided by 1 + cos ϕ.
This work was supported by the Deutsche Forschungsgemeinschaft, grant Kl 655/8-2, and by the Spezialforschungsbereich Optimierung und Kontrolle.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
O. Aichholzer, F. Aurenhammer, C. Icking, R. Klein, E. Langetepe, and G. Rote. ϕ-self-approaching curves. Technical Report 226, Department of Computer Science, FernUniversität Hagen, Germany, 1997. Submitted for publication.
H. Alt, B. Chazelle, and R. Seidel, editors. Computational Geometry. Dagstuhl-Seminar-Report 109. Internat. Begegnungs-und Forschungszentrum für Informatik, Schloss Dagstuhl, Germany, March 1995.
S. Arya, G. Das, D. M. Mount, J. S. Salowe, and M. Smid. Euclidean spanners: short, thin, and lanky. In Proc. 27th Annu. ACM Sympos. Theory Comput., pages 489–498, 1995.
H. P. Croft, K. J. Falconer, and R. K. Guy. Unsolved Problems in Geometry. Springer-Verlag, 1990.
C. Icking and R. Klein. Searching for the kernel of a polygon: A competitive strategy. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 258–266, 1995.
C. Icking, R. Klein, and E. Langetepe. Self-approaching curves. Technical Report 217, Department of Computer Science, FernUniversität Hagen, Germany, 1997. To appear in Mathematical Proceedings of the Cambridge Philosophical Society.
J.-H. Lee and K.-Y. Chwa. Tight analysis of a self-approaching strategy for online kernel-search problem. Technical report, Department of Computer Science, KAIST, Taejon, Korea, 1998
J.-H. Lee, C.-S. Shin, J.-H. Kim, S. Y. Shin, and K.-Y. Chwa. New competitive strategies for searching in unknown star-shaped polygons. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 427–429, 1997.
A. López-Ortiz and S. Schuierer. Position-independent near optimal searching and on-line recognition in star polygons. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 445–447, 1997.
G. Rote. Curves with increasing chords. Mathematical Proceedings of the Cambridge Philosophical Society, 115(1):1–12, 1994.
J. Ruppert and R. Seidel. Approximating the d-dimensional complete Euclidean graph. In Proc. 3rd Canad. Conf. Comput. Geom., pages 207–210, 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aichholzer, O., Aurenhammer, F., Icking, C., Klein, R., Langetepe, E., Rote, G. (1998). Generalized Self-Approaching Curves. In: Chwa, KY., Ibarra, O.H. (eds) Algorithms and Computation. ISAAC 1998. Lecture Notes in Computer Science, vol 1533. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49381-6_34
Download citation
DOI: https://doi.org/10.1007/3-540-49381-6_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65385-1
Online ISBN: 978-3-540-49381-5
eBook Packages: Springer Book Archive