Ponder This

November 2003

<<October November December>>

Solution:

Let K ⊂ R² be a convex compact body of perimeter 2q and diameter d. Let r be a positive integer. As Sn(K, r) we denote the smallest number s such that for any curve φ ⊂ K of length greater than s there is a line intersecting the curve φ in at least r + 1 different points.

We will first show:

Sn(K, r) ≥ rq, if r is even;

Sn(K, r) = (r - 1)q + d, if r is odd.

Fix the compact K and the number r. Let 2q be the perimeter of K and d be the diameter of K. Put s = rq if r is even and s = (r - 1)q + d if r is odd.

Let φ : [0; 1] → K be the curve of length greater than s. By the definition of the length we can choose the numbers 0 = α₀ < · · · < α_n = 1 such that the length of the broken line with the sequence of vertices φ(α₀), . . . , φ(α_n) is greater than s. Let l₁, . . . , l_n be the lengths of the segments of the broken line and α₁, . . . , α_n be the angles with these segments and the x-axis. For an angle θ ∈ [0;2π] as l(θ) we denote the sum of the lengths of the projections of the segments l_i onto the line L_θ = {(x, y) : (x, y) = (t cos θ, t sin θ)}. Thus l(θ) = ∑l_i| cos(θ - α_i)|. As k(θ) we denote the length of the projection of K onto the line L_θ. We shall need the following fact.

Fact.

∫	2π	k(θ)dθ = 4q
	0

Remark that for every ε > 0 there is a convex polygon K_ε of perimeter 2q_ε such that |q - q_ε| < ε and for each θ ∈ [0;2π] holds |k_ε(θ) - k(θ)| < θ where k_ε is the length of the projection of K_ε onto the line L_α. Hence it suffices to prove the fact only in the case when K is a convex polygon. Let k₁, . . . , k_n be the lengths of the segments of the broken line and α₁, . . . , α_n be the angles with these segments and the x-axis. Then

∫	2π	k(θ)dθ =
	0

1	∫	∑	2π	ki|cos(θ - αi)|dθ =
2			0

1	∑	∫	2π	ki|cos(θ - αi)|dθ =
2			0

1	∑	∫	2π	ki|cos(β)|dβ =
2			0

2	∑	ki = 4q

Now we are able to prove the bounds. At first suppose that r is even. To the rest of the proof it suffices to show that there is an angle θ' such that l(θ') > rk(θ'). Suppose the contrary. Then

4rq =

r	∫	2π	k(θ)dθ ≥
		0

∫	2π	l(θ)dθ =
	0

∫	2π	l(θ)dθ =
	0

∫	2π	∑	li|cos(θ - αi)|dθ =
	0

∑	∫	2π	li|cos(θ - αi)|dθ =
		0

∑	∫	2π	li|cos(β)|dβ =
		0

∑4l_i > 4s = 4rq

The contradiction.

Now suppose that r is odd. Add to the broken line the segment connecting its ends. Let the length of the segment be l₀ and θ₀ be the angle with the segment and the x-axis. To the rest of the proof it suffices to show that there is an angle θ' such that l(θ') > rl₀| cos(θ')| + (r - 1)(k(θ') - l₀| cos(θ')|) = (r - 1)k(θ') + l₀| cos(θ')|. That is because each line not intersecting l₀ and the vertices of the broken line intersects the broken line an even number of times.

Suppose the contrary. Then

4(r-1)q+4l₀ =

∫	2π	(r-1)k(θ)+l0|cos(θ)|dθ ≥	∫	2π	l(θ)dθ =
	0			0

∫	2π	∑	li|cos(θ-αi)|dθ =
	0

∑	∫	2π	li|cos(α-αi)|dα =
		0

∑	∫	2π	li|cos(β)|dβ =
		0

∑4l_i > 4s = 4rq + 4d

Which yields the contradiction since l₀ ≤ d.

The matching lower bounds: if r is even, let the curve go r/2 times around the perimeter, curving slightly to avoid any straight lines but remaining convex. The attached picture illustrates the case where K is a square (rather than a pentagon). If r is odd, let the curve go almost (r-1)/2 times around the perimeter, then down the diagonal, again always curving slightly. The 2 reason we go "almost" (r-1)/2 times around the perimeter is to ensure that any straight line L which intersects this curved diagonal twice, will intersect the perimeter-curve at most r - 2 times rather than r - 1.

For our particular case, r = 5, 2q = 5, and d = 2sin(2π/10) = 1.618, so that the bound is (r - 1)q + d = 11.618.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com