Technische Universität Graz Institut für Mathematik Christian-Doppler-Laboratorium ”Diskrete Optimierung“

Curves with Increasing Chords

Günter Rote

Report 245  April 1993  CDLDO-11

Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria

Version 2 This report appeared in the Mathematical Proceedings of the Cambridge Philosophical Society 115 (1994), 1–12.

Title page processed by TEX on February 14, 1995

Curves with Increasing Chords

Günter Rote

Institut für Mathematik, Technische Universität Graz Steirergasse 30, A-8010 Graz, Austria

received 16 February 1993;

Abstract

A curve has increasing chords if AD ≥ BC for any four points A, B, C, D lying on the curve in that order. The length of such a curve that connects two points at distance 1 is at most 2π/3 in two dimensions, which is the optimal bound, and less that 30 in three dimensions.

AMS 1991 Mathematics Subject Classifications: 52A40 (51K99, 51M04, 51M25, 52A38)

1 Introduction

Let \overline{AB} denote the Euclidean distance between two points A and B. If f: [0, 1] → ℝ^{n} is a curve, f[t_{1}, t_{2}] denotes the part of the curve between f(t_{1}) and f(t_{2}), and length(f[t_{1}, t_{2}]) denotes its length. The length of the whole curve is denoted by length(f).

Definition. Let f: [0, 1] → ℝ^{n} be an n-dimensional curve.

1. f has increasing chords, if for 0 ≤ t_{1} ≤ t_{2} ≤ t_{3} ≤ t_{4} ≤ 1, \overline{f(t_{1})f(t_{4})} ≥ \overline{f(t_{2})f(t_{3})}.

2. The minimum growth rate of f is

inf \{ \frac{\overline{f(t_{1})f(t_{2})}}{length(f[t_{1}, t_{2}])} : 0 ≤ t_{1} < t_{2} ≤ 1 \} ,

if f is rectifiable and 0 otherwise.

The conditions in these definitions express some sort of “smoothness” of the curves, although piecewise linear curves are not forbidden. Definition 2 contains the minimum growth rate as a numerical parameter, and thus it allows us to express various “degrees” of smoothness of curves. In this paper we investigate relations between these concepts of smoothness.

Larman and McMullen [2] showed that the minimum growth rate of a plane curve with increasing chords is at least 1/\sqrt{12} ≈ 0.289 and indicated how this bound can be improved to approximately 0.3. They conjectured that the true lower bound is \frac{3}{2π} ≈ 0.477, which is the minimum growth rate of two 60^{∘} arcs around the endpoints f(0) and f(1), see figure 1. This conjecture is mentioned as problem G3 in the book of Croft, Falconer, and Guy [1].

A f B

Figure 1: The longest path with increasing chords between A and B

We prove this conjecture, and we bound the minimum growth rate of curves with increasing chords in higher dimensions.

The results in this paper have applications in the context of piecewise linear approximations of a curve, where the above concepts are used to define “well-behaved” curves for which simple algorithms suffice to compute good or optimal approximations because certain anomalies cannot arise, see Rote and Tichy [3]. For the correctness of a certain greedy-like approximation algorithm we needed a condition which prevents the curve from going from a point A to a distant point B and returning to A again while remaining inside a narrow, infinitely long cylinder. In other words, the curve is not allowed to “turn around” inside a narrow cylinder. On the other hand, we did not want to exclude polygonal curves, because very often the curves are given in a discretized, i. e., polygonal way. So the simple idea of bounding the curvature cannot be applied. We also did not want to exclude a curve which closes itself after making a “large” turn. One way to restrict curves in a meaningful manner with respect to the mentioned aims is to impose any one of the conditions 1–2 in the above definition locally, i. e., only for points f(t_{1}), f(t_{2}), … whose distance along the curve is smaller than some specified bound.

2 Increasing Chords in The Plane

Theorem 1 The minimum growth rate of a plane curve with increasing chords is at least \frac{3}{2π}.

Proof: Let f: [0, 1] → ℝ^{2} be our curve with increasing chords, starting at A = f(0) and ending at B = f(1). It is sufficient to show that length(f) ≤ \frac{2π}{3} · \overline{AB}.

By the definition of curve length,

length(f) := sup ∑_{i=1}^{m} \overline{f(t_{i−1})f(t_{i})},  (1)

where the supremum is taken over all subdivisions 0 = t_{0} < t_{1} < t_{2} < ⋯ < t_{m−1} < t_{m} = 1 of the curve.

Let me first give an overview of the proof. We take any fixed subdivision as above. In the first step we will simplify f and replace it by a more manageable curve g from A = f(0) to B = f(1) which goes through the points f(t_{1}), f(t_{2}), … in that order, and whose length is at most the length of f (and of course bigger than the sum on the right side of (1)). In particular, each piece of g between f(t_{i}) and f(t_{i+1}) consists of at most one convex piece turning to the left, one straight segment, and one convex piece turning to the right, in that order or in the reverse order. Still, we ensure that g has increasing chords.

In the second step we follow an idea that was also used in Larman and McMullen [2]: We convexify g and obtain a convex curve g̃ with the same endpoints and with the same length as g. Intuitively, we cut g into small pieces and rearrange them according to decreasing slope.

In the third step we show that this curve lies in the intersection of the two disks with radius 1 centered at A and B. The curve length is therefore bounded by the length of the two upper 60^{∘} arcs of the two circles, and we are done. In this step we will have to establish a correspondence between pieces of g̃ and pieces of g, and there the above-mentioned properties of the simplified curve g will help us.

Below we will discuss the three steps in detail. We will assume w. l. o. g. that A = f(0) = (0, 0) and B = f(1) = (1, 0). Let us state the following easy lemma, which is already given in Larman and McMullen [2].

Lemma 1 The curve f is strictly monotone in the x-direction, i. e., if f(t) = \binom{x(t)}{y(t)}, then 0 ≤ t_{1} < t_{2} ≤ 1 implies x(t_{1}) < x(t_{2}).

Let us use the notation A_{i} = f(t_{i}). In the first step of the proof we look at each part f[t_{i}, t_{i+1}] of the curve in turn and replace it by the shortest possible curve between A_{i} and A_{i+1} such that the new piece together with the original curve from A to A_{i} and from A_{i+1} to B still has increasing chords. We say that a curve f: [a, b] → ℝ^{2} has increasing chords with respect to some set S if for all P ∈ S and for all a ≤ t_{1} ≤ t_{2} ≤ b, \overline{P f(t_{1})} ≤ \overline{P f(t_{2})}.

Lemma 2 A curve f has increasing chords with respect to a set S if and only if it has increasing chords with respect to the convex hull of S.

Proof: For a ≤ t_{1} < t_{2} ≤ b with f(t_{1}) ≠ f(t_{2}), the bisector of f(t_{1}) and f(t_{2}) divides the plane into two halfplanes. The curve f has increasing chords with respect to S if and only if for all a ≤ t_{1} < t_{2} ≤ b with f(t_{1}) ≠ f(t_{2}), the closed halfplane bounded by the bisector on the side of f(t_{1}) contains S. From this the lemma follows immediately.

We want our new curve g_{i} from A_{i} to A_{i+1} to have increasing chords with respect to f[0, t_{i}]. It is therefore sufficient to look at the convex hull C of f[0, t_{i}], see figure 2. The area where g is allowed to run from A_{i} to A_{i+1} is bounded by the two convex smooth involutes of C starting at A_{i} that are generated by a string that is unrolled around C. In addition, this area is bounded by the two involutes of the convex hull of f[t_{i+1}, 1] starting at A_{i+1}. We take g_{i} to be the shortest curve from A_{i} to A_{i+1} which does not cross the four involute boundaries. Obviously the curve f[t_{i}, t_{i+1}] must fulfill this condition, and therefore g_{i} exists.

The following lemma states a couple of quite intuitive properties of the curves, whose formal proof is nevertheless relatively long.

A  C  f  A_{i} g_{i} A_{i+1}  f  B

Figure 2: Replacing the part of the curve between A_{i} and A_{i+1} by a new curve g_{i}

Lemma 3 (i) The typical shape of g_{i} consists of

(1) an initial piece of one of the involutes starting in A_{i},

(2) a straight-line segment, and

(3) an initial piece of one of the involutes starting in A_{i+1},

in the given order. Parts (1) and (3) may be missing. If any of (1) or (3) is present, the segment (2) is tangent to it. The segment (2) may also be missing in the extreme cases that parts (1) and (3) are tangent to each other or that part (1) goes through A_{i+1} or part (3) goes through A_{i}. If parts (1) and (3) are both present they turn in opposite directions.

(ii) Parts (1) and (3) of the curve each turn by less than 90^{∘}.

(iii) The curve g_{i} has increasing chords with respect to f[0, t_{i}].

(iv) The inverse curve of g_{i} has increasing chords with respect to f[t_{i+1}, 1].

(v) The curve g_{i} itself has increasing chords (“with respect to itself”, so-to-speak).

(vi) The curve g_{i} is not longer than f[t_{i}, t_{i+1}].

(vii) The convex hull of g_{i} is contained in the convex hull of f[t_{i}, t_{i+1}].

Proof: Statement (i) follows directly from the fact that the involutes are convex and bend outwards.

To see (ii), let β⃗ be the initial tangent direction of g_{i} at A_{i}, and let β⃗′ be the normal direction pointing towards the inner (concave) side of the involute. Now consider a point T on part (1) of the curve g_{i} where the tangent direction has turned by 90^{∘} and is parallel to β⃗′. By the properties of an involute, there is either a single point P on the curve f[0, t_{i}] lying on the concave (inner) side of the involute, such that the angle between \overrightarrow{P A_{i}} and β⃗ is 90^{∘}, or there is a sequence P_{j} of points approaching A_{i} such that the corresponding angle approaches 90^{∘}. In the first case, T must lie at least as far in the direction β⃗′ as P, and it follows that \overline{P T} < \overline{T A_{i}}. In the second case, the same relation holds for some point P_{j} which is close enough to A_{i} and whose angle is close enough to 90^{∘}.

Now, T is used by g_{i}, and this means that the curve f[t_{i}, t_{i+1}] must necessarily cross the ray from T in the tangent direction β⃗′ in some point T′ in order to reach A_{i+1}. The distance of T′ from A_{i} is bigger than its distance from P or P_{j}, respectively, and this contradicts the increasing chord property.

Statement (iii) is true for part (1), because the involute has this property: C is always contained on one side of the normal line of the curve. When the curve changes from part (1) to part (2), the normal line of g, which was previously tangent to C, moves away from C, and hence the distance from C increases. This holds also if part (1) is missing. When part (3) of the curve starts, the normal line turns even further away from C. The only thing that can happen is that the normal line hits C on the other side of the curve, but this can also be excluded: It would mean that the normal line q contains the following three points in the given order: The current point P on the involute, the point on f[t_{i+1}, 1] which is the center about which the involute currently rotates, and an extreme point of C, i. e., a point of f[0, t_{i}]. As P is used by g_{i}, it means that f[t_{i}, t_{i+1}] must intersect q in a point which lies before P (in the above order on q). The three points of f on q now clearly violate the increasing chord property.

Statement (iv) is analogous to (iii), and (v) follows easily from (i) and (ii).

Statement (vi) is clear from the definition of g, and (vii) can be seen by considering the possible shapes of g_{i} according to (i) and the possible paths that f[t_{i}, t_{i+1}] can take.

By (vii) and lemma 2, each curve g_{i} has not only increasing chords with respect to the other parts of f, but also with respect to the other pieces g_{k}. Therefore we can put together the pieces g_{1}, g_{2}, …, and we obtain a curve g with the desired properties: It has increasing chords, its length lies between ∑_{i=1}^{m} \overline{f(t_{i−1})f(t_{i})} and the length of f, and it consists of finitely many convex pieces and straight line segments. In the remainder of the proof we will only work with the simplified curve g.

In the second step we convexify the curve g: [0, 1] → ℝ^{2}. The idea is to cut g into infinitesimal pieces and rearrange them according to slope. Since g has finitely many convex pieces we need not worry about problems with limits and we can give an explicit construction for the convexified curve g̃.

Formally, let 0 = t_{0} < t_{1} < t_{2} < ⋯ < t_{m−1} < t_{m} = 1 be a subdivision of g such that each piece g[t_{i−1}, t_{i}] is either a straight line segment, strictly convex, or strictly concave (when viewed as a function of x). The convexified curve g̃: [0, U] → ℝ^{2} will be parameterized by a parameter u in the following way: For every piece g[t_{i−1}, t_{i}] there are two points r_{i}(u) and s_{i}(u) in the interval [t_{i−1}, t_{i}] that vary continuously and monotonically with u. Initially, r_{i}(0) = s_{i}(0). Then r_{i} decreases with u and s_{i} increases with u until [r_{i}(U), s_{i}(U)] = [t_{i−1}, t_{i}]. Moreover, for each u there exists a direction α(u) in the range [−π/2, π/2] (when measured by its angle with the positive x-axis) such that for every i, g[r_{i}(u), s_{i}(u)] is precisely that piece of g[t_{i−1}, t_{i}] which is steeper than α(u) (in the sense of having larger slope).

More precisely, let α′ be the vector pointing in the direction 90^{∘} counterclockwise from α, i. e., into the upper half-plane. If g[t_{i−1}, t_{i}] is strictly concave (as a function of x), we have r_{i}(u) = t_{i−1} and

s_{i}(u) = arg max_{t_{i−1}≤s≤t_{i}}⟨α′, g(s)⟩.

If g[t_{i−1}, t_{i}] is strictly convex, then s_{i}(u) = t_{i} and

r_{i}(u) = arg min_{t_{i−1}≤r≤t_{i}}⟨α′, g(r)⟩.

For a straight segment g[t_{i−1}, t_{i}], we can for example set r_{i}(u) = s_{i}(u) = t_{i} as long as α(u) is steeper than the segment. Then there is an interval [u, u′] during which α(u) remains stationary and parallel to the segment. In this interval r_{i}(u) decreases to t_{i−1}. For higher values of u, r_{i}(u) and s_{i}(u) remain constant again.

Clearly, α(u) is decreasing. It is easy to construct such parameterizations α(u), r_{i}(u), and s_{i}(u). Were it not for the straight pieces of g, we could take α itself as the parameter. We can also ensure that α(u) is continuous.

The curve g̃: [0, U] → ℝ^{2} is now defined by the following equation.

\overrightarrow{Ag̃(u)} = ∑_{i=1}^{m} \overrightarrow{g(r_{i}(u))g(s_{i}(u))}.  (2)

This is only a weakly monotonic parameterization of the curve. It is clear that g̃ is a curve from A to B. It is convex because in each point g̃(u) the line with direction α(u) is a supporting line. The curve g̃ lies in the upper half-plane, and moreover, it has the same length as g. This is due to the following fact: As u increases by a small amount the parts of g that are added to g̃ are essentially parallel.

\overrightarrow{g̃(u)g̃(u + ε)} = ∑_{i=1}^{m} \overrightarrow{g(r_{i}(u + ε))g(r_{i}(u))} + ∑_{i=1}^{m} \overrightarrow{g(s_{i}(u))g(s_{i}(u + ε))}.

The direction of the non-zero vectors in this sum lies in the range [α(u + ε), α(u)]. Thus the length of the vector sum differs from the sum of the lengths of the vectors by at most a factor of cos(α(u) − α(u + ε)), which can be made arbitrarily close to 1.

In the third step of the proof, we show that each point of the curve g̃ has distance at most 1 from A and B. Assume the contrary, for example that the largest distance from B is bigger than 1. Then there must be a point T on g̃ different from A with a supporting line of direction α such that the normal to α through T passes above B, see figure 3. We take α in the direction of the curve g̃ running from A to B, and we find a parameter value u such that α(u) is this direction. According to the representation (2), we can cut the curve g into parts at the points r_{j}(u) and s_{j}(u). We get two kinds of parts: The “upward” parts g[r_{j}(u), s_{j}(u)], where the slope is always bigger than α, and the remaining “downward” parts g[s_{j−1}(u), r_{j}(u)], g[0, s_{1}(u)], and g[t_{m}(u), 1], where the slope is smaller. By discarding empty “parts” and merging together adjacent non-empty parts which are all upward or which are all downward we can assume that upward and downward parts alternate on the curve, and that the parts are proper parts of positive length. The sum of the upward vectors is \overrightarrow{AT}, by (2), and the downward vectors sum to \overrightarrow{T B}. Since the inner product ⟨\overrightarrow{T B}, α⟩ < 0, there must be a downward part g[u, v] whose starting point g(u) lies higher in the α direction than its endpoint g(v). This part must be adjacent to some upward part (see figure 4, where the case of an upward part which precedes g[u, v] is shown). However, this leads to a contradiction with the

A T  α  g̃  B

Figure 3: How the curve exits the circle of radius 1 around B

increasing chord property: As one moves away from the common subdivision point on the upward part (in figure 4 this is the point g(u)), the distance to the other endpoint (g(v) in the figure) of the downward part decreases.

Now the proof of theorem 1 is complete: the longest convex curve from A to B which is contained in the intersection of the two disks follows the boundary of this intersection, as in figure 1, and this length is 2π/3.

Note that a curve with a positive minimum growth rate less than 1 does not necessarily have increasing chords, as the example of a sufficiently fast winding logarithmic spiral shows.

3 Higher Dimensions

We will now establish a positive lower bound on the growth rate of a curve with increasing chords in three and higher dimensions. Since the proof for three dimensions contains all the essential ideas, we will first prove this case in sufficient detail and derive an explicit bound.

First we need a lemma. We say that a curve is monotone in the direction of a vector a if the inner product ⟨f(t), a⟩ increases along the curve.

Lemma 4 Suppose that a curve f: [0, 1] → ℝ^{n} from f(0) = A to f(1) = B is monotone in the linearly independent directions q^{1}, q^{2}, …, q^{n}. Then the curve is contained in the parallelotope (parallelepiped)

P = { x ∈ ℝ^{n} : ⟨A, q^{i}⟩ ≤ ⟨x, q^{i}⟩ ≤ ⟨B, q^{i}⟩ for i = 1, …, n },

and its length is bounded by the length of n successive edges of P leading from A to B.

Proof: First of all it is clear that the curve is contained in P and that the path formed by n successive edges of P is monotone in the directions q^{1}, q^{2}, …, q^{n}. Therefore the claimed bound can actually be achieved.

g(u) α g g(v)

Figure 4: Deriving the contradiction to the increasing chord property

Let Q be the matrix whose rows are the vectors q^{1}, q^{2}, …, q^{n}, and transform the coordinates x of the curve by

x̄ = Qx.

Let us denote the basis vectors of the transformed coordinate system (the columns of Q^{−1}) by r_{i}. We may w. l. o. g. normalize the vectors q^{i} in such a way that the vectors r_{i} are unit vectors. The transformed coordinates x̄^{i} are just the scalar products with the directions q^{i}:

x̄^{i} = ⟨x, q^{i}⟩.

By assumption, these coordinates increase monotonically along the curve f, and therefore we may parameterize the curve by u := x̄^{1} + x̄^{2} + ⋯ + x̄^{n}. Let us assume that f: [u_{0}, U] → ℝ^{n} is this parameterization.

Now take any subdivision u_{0} < u_{1} < u_{2} < ⋯ < u_{m} = U of the parameter interval and consider the length of the corresponding polygonal path.

L := ∑_{j=1}^{m} \overline{f(u_{j−1})f(u_{j})}.  (3)

Let us look at one term of this sum, for fixed values of u_{j−1} and u_{j} with Δu := u_{j} −u_{j−1}, and consider the maximum possible value of \overline{f(u_{j−1})f(u_{j})} for a given Δu. Let Δx̄ denote the difference between the transformed coordinates of f(u_{j}) and f(u_{j−1}): Δx̄ := Q(f(u_{j}) − f(u_{j−1})). Then we have for the coordinates Δx̄^{i} of Δx̄:

Δx̄^{i} ≥ 0, for i = 1, …, n, and

Δx̄^{1} + Δx̄^{2} + ⋯ + Δx̄^{n} = Δu. (4)

The vector \overrightarrow{f(u_{j−1})f(u_{j})} whose norm we want to maximize is given by

\overrightarrow{f(u_{j−1})f(u_{j})} = Q^{−1} · Δx̄ = ∑_{i=1}^{n} Δx̄^{i} · r_{i}.

The possible resulting vectors \overrightarrow{f(u_{j−1})f(u_{j})} subject to the constraints (4) form a simplex with vertices Δu · r_{i}. Since the norm is a convex function, it takes its maximum at one of the vertices of the feasible region. In our case, all vertices maximize the norm: their length is Δu = u_{j} − u_{j−1}. So we obtain for (3)

L = ∑_{j=1}^{m} \overline{f(u_{j−1})f(u_{j})} ≤ ∑_{j=1}^{m}(u_{j} − u_{j−1}) = U − u_{0},

and the maximum is obtained when every segment f(u_{j−1})f(u_{j}) is parallel to one of the edge directions q^{i}.

Larman and McMullen [2] used a special case of this lemma in two dimensions. They proved it by a more direct argument, rearranging segments according to slope as we did in the second step of the proof of theorem 1.

We will now specialize this lemma to three dimensions and we will actually compute the maximum possible length of the curve for three vectors q^{1}, q^{2}, and q^{3} in a special position.

Lemma 5 Suppose that a three-dimensional curve f: [0, 1] → ℝ^{3} from f(0) = A to f(1) = B is monotone in the three directions q^{1}, q^{2}, and q^{3}, where q^{3} = \overrightarrow{AB}, the angle between q^{1} and q^{2} is π/3 and the angle between q^{3} and the plane spanned by q^{1} and q^{2} is π/3. Then the length of the curve is at most

(\sqrt{4/3} + \sqrt{13/12} ) · \overline{AB} ≈ 2.2 · \overline{AB}.

Proof: We assume w. l. o. g. that q^{1}, q^{2}, and q^{3} are unit vectors, q^{1} is parallel to the x-axis, and q^{2} lies in the x-y-plane. The matrix Q in the previous theorem whose rows are the vectors q^{i} can thus be written as follows:

Q = (\begin{matrix}q^{1} \\ q^{2} \\ q^{3} \end{matrix}) = (\begin{matrix}1 & 0 & 0 \\ cos(π/3) & sin(π/3) & 0 \\ cos(π/6 + ϕ) cos(π/3) & sin(π/6 + ϕ) cos(π/3) & sin(π/3) \end{matrix}) ,

where π/6 + ϕ is the angle that the projection of q^{3} on the x-y-plane makes with the x-axis. We have

R = Q^{−1} = (r_{1}, r_{2}, r_{3}) = (\begin{matrix}1 & 0 & 0 \\ −1/\sqrt{3} & 2/\sqrt{3} & 0 \\ −2 sin(π/6 − ϕ)/3 & −2 sin(π/6 + ϕ)/3 & 2/\sqrt{3} \end{matrix}) .

The lengths of the edges of the parallelotope P are given by ∥r_{i}∥⟨q^{i}, q^{3}⟩/∥q^{3}∥, because the projection of the edge parallel to r_{i} onto q^{i} is equal to the projection of \overrightarrow{AB} = q^{3} onto q^{i}. After some computation and straightforward manipulations we obtain the following expression for the sum of the three edges:

(\sqrt{12} + cos(π/6+ϕ) \sqrt{4 − cos(π/6−ϕ)^{2}} + cos(π/6−ϕ) \sqrt{4 − cos(π/6+ϕ)^{2}} ) / 3 (5)

Neglecting constant terms and factors, this expression is of the form

b\sqrt{4 − a^{2}} + a\sqrt{4 − b^{2}},  (6)

with a = cos(π/6 + ϕ) and b = cos(π/6 − ϕ). For any fixed a in the range −1 ≤ a ≤ 1, the value of b in the range −1 ≤ b ≤ 1 which maximizes this expression is b = 1. Substituting this value into (6) and maximizing a, one sees that the maximum is achieved for a = b = 1. Since a and b are cosines this means that the angles must be zero: π/6 + ϕ = π/6 − ϕ = 0. Substituting the value ϕ = 0 into (5) gives the bound claimed in the lemma.

Lemma 6 Suppose that a three-dimensional curve f: [0, 1] → ℝ^{3} from f(0) = A to f(1) = B has increasing chords and is monotone in two directions q^{1} and q^{2}, where q^{2} = \overrightarrow{AB} and the angle between q^{1} and q^{2} is π/3. Then the length of the curve is at most

(1 + 1/\sqrt{12}) (4 + \sqrt{13}) · \overline{AB} ≈ 9.8 · \overline{AB}.

Proof: Let us assume w. l. o. g. that q^{1} = (1, 0, 0) and q^{2} = \overrightarrow{AB} = (1/2, \sqrt{3}/2, 0). Let 0 = t_{0} < t_{1} < t_{2} < ⋯ < t_{m−1} < t_{m} = 1 be any subdivision of the curve. We shall refine this subdivision by inserting additional points. What we want is the following property: We classify the segments f(t_{i})f(t_{i+1}) into steep and flat ones, as the angle between the segment and the x-y-plane is ≥ π/3 or < π/3. For each steep segment f(t_{i})f(t_{i+1}), we will be able to find points t_{j} and t_{k} with j ≤ i and k ≥ i + 1 such that the angle between the segment f(t_{j})f(t_{k}) and the x-y-plane is exactly equal to π/3. Moreover, the covering intervals [t_{j}, t_{k}] that occur in this way should not overlap too much.

We go along the curve from A to B. We start by setting i = 0. If the current segment f(t_{i})f(t_{i+1}) is flat we proceed to the next segment, i. e., we increase i by 1. Otherwise we look for the last point f(t), with t > t_{i}, on the curve for which the angle between the segment f(t_{i})f(t) and the x-y-plane is equal to π/3. If the angle between f(t_{i})B and the x-y-plane is at most π/3, continuity ensures that such a point t exists. Geometrically, the set of points p for which the segment f(t_{i})p makes the desired angle is a circular cone with apex f(t_{i}). We look for the last intersection point f(t) of the curve with this cone. We insert this point into the subdivision, if necessary, and we declare [t_{i}, t] to be a covering interval. The next segment that we look at is the segment from f(t) to the next point on the given subdivision.

As indicated above, it is possible that there is so such intersection point following t_{i}. In this case we stop. The angle between the segment f(t_{i})B and and the x-y-plane must be larger than π/3. So we can find the first point f(t) on the curve for which the angle between f(t)B and the x-y-plane is equal to π/3. We must have t < t_{i}. We finally insert this point t into the subdivision, if necessary, and we declare [t, 1] to be a “special” covering interval.

It is now clear that the above desired properties of the subdivision hold: Every steep segment is covered by at least one covering interval. Moreover, the covering intervals are disjoint, with the possible exception of the last “special” covering interval.

Now we look at the projection of the curve onto the x-y-plane. We can apply lemma 4 in two dimensions, and we conclude that the length of this projected curve is at most cot(π/3) + 1/ sin(π/3) = \sqrt{3}.

For any covering interval [t_{j}, t_{k}] we call the segment f(t_{j})f(t_{k}) a covering segment. Let a denote the total length of the projections of all flat segments which are not covered by any covering interval. Let b denote the length of the projection of the last special covering segment. If that segment was not generated, we set b = 0. Let c denote the total length of the projections of all remaining covering segments. We have a + c ≤ \sqrt{3}, because the segments accounted for in a and c correspond to parts of the curve which do not overlap. Since no single segment can be longer than \overline{AB} = 1 we have b ≤ cos(π/3) = 1/2.

Now each flat segment whose projection has length l has length at most l/ cos(π/3) = 2l, giving an overall contribution of 2a. Each covering interval [t_{j}, t_{k}] gives rise to a piece of the curve to which lemma 5 can be applied: This piece of the curve is monotone in the direction q^{3} = \overrightarrow{f(t_{j})f(t_{k})} since the curve has increasing chords (lemma 1). If the two-dimensional projection of the covering segment f(t_{j})f(t_{k}) has length l, then that segment itself has length l/ cos(π/3) = 2l, and this must be multiplied by the factor from lemma 5. Hence the total contribution of all segments which are covered by covering segments is at most (b + c)(4/\sqrt{3} + \sqrt{13/3}). Every segment in the subdivision is now either accounted for in this bound or in the above bound 2a. Regarding the constraints on a, b, and c, the sum of the two bounds is maximized for c = \sqrt{3} and b = 1/2. This gives an overall bound of (\sqrt{3} + 1/2)(4/\sqrt{3} + \sqrt{13/3}) for the length of the curve.

Theorem 2 The minimum growth rate of a three-dimensional curve with increasing chords is at least

\frac{1}{(3 + \sqrt{3}/2) (4 + \sqrt{13})} ≈ \frac{1}{29.4} ≈ 0.034.

Proof: Similarly to the proof of lemma 6 we will classify the segments of a subdivision into steep and flat ones. By refining the subdivision we will ensure that every steep segment is covered by some covering interval. We will bound the length of the flat segments directly and reduce the covering intervals to lemma 6, just as the proof of lemma 6 reduced them to lemma 5. Since the proof is essentially the same as that of lemma 6 we will only sketch it, emphasizing the differences.

We know that the curve from A to B is monotone in the direction q^{1} = \overrightarrow{AB}. We assume w. l. o. g. that q^{1} = (1, 0, 0).

A segment of some subdivision of the curve is classified as steep or flat according to its angle with the direction q^{1}: It is called steep if this angle is at least π/3.

The process of introducing new points of the subdivision and declaring covering intervals is just as in lemma 6. Finally we project all segments onto the x-axis, and as before we denote by a, b, and c the total lengths of projections of uncovered flat segments, of the special covering segment, and of the remaining covering segments, respectively. We have a + c ≤ 1 and b ≤ cos(π/3) = 1/2.

We divide the bound 3/2 on a+b+c by cos(π/3) to take into account the projection and multiply the result by the factor from lemma 6, giving the bound (3+\sqrt{3}/2)(4+\sqrt{13}) for the overall length of the curve.

By choosing different threshold angles in the definitions of steep and flat segments one can slightly improve the constant of theorem 2. The best bound that can be obtained by the above proof method is 29.28. It is achieved by choosing an angle of 1.07 instead of π/3 in lemma 6, and an angle of 1.003 instead of π/3 in lemma 5.

It is in principle no problem to extend the above proof to more than three dimensions.

Theorem 3 For every n, there is a positive lower bound on the minimum growth rate of an n-dimensional curve with increasing chords.

Proof: (Sketch.) One inductively establishes an upper bound on the length of an ndimensional curve with increasing chords from A to B which is monotone in i linearly independent directions q^{1}, q^{2}, …, q^{i}, where \overrightarrow{AB} = q^{i} has length 1 and for each j, the angle between q^{j} and the subspace spanned by q^{1}, q^{2}, …, q^{j−1} is π/3. This is proved by induction from i = n down to i = 1. The induction basis (i = n) is provided by lemma 4. The induction proceeds as above from lemma 4 and lemma 5 over lemma 6 to theorem 2. At every step, segments are classified as steep and flat ones according to their angle with the subspace spanned by q^{1}, q^{2}, …, q^{i}. The last case (i = 1) gives the statement of the theorem, by lemma 1.

4 Lower Bounds

As a generalization of the planar case to n dimensions, it has been proposed that the curve with increasing chords which has the largest growth rate is given by n successive edges of a Reuleaux simplex. A Reuleaux simplex is obtained as the intersection of n + 1 unit balls centered at the vertices of an n-dimensional regular simplex with side length 1. The total length of three edges of a Reuleaux tetrahedron in three dimensions is about 3.20, which is very far from the bound 29.4 in theorem 2. However, this curve does not satisfy the increasing chord property: Let A_{0}, A_{1}, A_{2}, A_{3} denote the vertices of the Reuleaux tetrahedron, in the order in which they are visited. The “edge” from A_{0} to A_{1} is a circular arc in the bisecting plane of A_{2} and A_{3}, centered at the midpoint of the segment A_{2}A_{3}. Let A_{0.5} be the point on this edge which is equidistant from A_{0} and A_{1}, and similarly, let A_{2.5} be the point on the edge between A_{2} and A_{3} which is equidistant from these two points. Then the distance between A_{0.5} and A_{2.5} is \sqrt{3} − \sqrt{1/2} ≈ 1.025 > 1, and thus the increasing chord property is violated. By slightly pushing the points A_{0.5}, A_{1}, A_{2}, and A_{2.5} towards the center one can construct a modified curve which consists of five pieces which are circular arcs that lie in the same planes as in the original construction, and which does have increasing chords. Its length is about 3.087, but the construction can surely be modified to yield a longer curve.

Note that lemma 4 in some sense gives an indication what a longest curve with increasing chords might look like: Lemma 4 says that a curve that is constrained to be monotone in certain directions achieves its maximum length when it always moves in one of its extreme possible directions. Locally, the curve of figure 1 behaves everywhere exactly in this way, when the monotonicity directions that are implied by the increasing chord property with respect to the other edges are taken into account. The same holds (approximately) for the n edges of a Reuleaux simplex.

References

[1] Hallard T. Croft, Kenneth J. Falconer and Richard K. Guy. Unsolved Problems in Geometry. (Springer-Verlag, 1991).

[2] David G. Larman and Peter McMullen.

Arcs with increasing chords. Proc. Cambridge Philos. Soc. 72 (1973), 205–207.

[3] Günter Rote and Robert F. Tichy.

Spherical dispersion with an application to polygonal approximation of curves. To appear in Anzeiger der Österreichischen Akademie der Wissenschaften (1994/1995).