Generalized self-approaching curves

被引:21
作者
Aichholzer, O
Aurenhammer, F
Icking, C
Klein, R
Langetepe, E [1 ]
Rote, G
机构
[1] Graz Tech Univ, A-8010 Graz, Austria
[2] Free Univ Berlin, Inst Informat, D-14195 Berlin, Germany
[3] Fern Univ Hagen, D-58084 Hagen, Germany
关键词
self-approaching curves; convex hull; detour; arc length;
D O I
10.1016/S0166-218X(00)00233-X
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We consider all planar oriented curves that have the following property depending on a fixed angle p. For each point B on the curve, the rest of the curve lies inside a wedge of angle p with apex in B. This property restrains the curve's meandering, and for p less than or equal to pi /2 this means that a point running along the curve always gets closer to all points on the remaining part. For all p<<pi>, we provide an upper bound c(p) 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 p. (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:3 / 24
页数:22
相关论文
共 10 条
[1]  
ALT H, 1995, COMPUTATIONAL GEOMET
[2]  
[Anonymous], 1991, P 3 CANADIAN C COMPU
[3]  
Arya S., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, P489, DOI 10.1145/225058.225191
[4]  
Croft H. P., 1990, UNSOLVED PROBLEMS GE
[5]   Self-approaching curves [J].
Icking, C ;
Klein, R ;
Langetepe, E .
MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1999, 125 :441-453
[6]  
Icking C., 1995, Proceedings of the Eleventh Annual Symposium on Computational Geometry, P258, DOI 10.1145/220279.220307
[7]   Tight analysis of a self-approaching strategy for the online kernel-search problem [J].
Lee, JH ;
Chwa, KY .
INFORMATION PROCESSING LETTERS, 1999, 69 (01) :39-45
[8]  
LEE JH, 1997, P 13 ANN ACM S COMP, P427
[9]  
Lopez-Ortiz A., 1997, Proceedings of the Thirteenth Annual Symposium on Computational Geometry, P445, DOI 10.1145/262839.263077
[10]   CURVES WITH INCREASING CHORDS [J].
ROTE, G .
MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1994, 115 :1-12