Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 39 (1998), No. 2, 447-459.

Solution Branching of a General Perimeter Partition Problem

Anita Kripfganz

Institut für Mathematik, Universität Leipzig, Augustusplatz 10, 04109 Leipzig, Germany e-mail: kripfganz@mathematik.uni-leipzig.de

Abstract. In generalization of an isoperimetric partition problem m-tuples of plane figures are considered. Each of them is inscribed in a unit circular sector with the same central angle. Their total perimeter length is fixed while minimizing the total area. The appearing solution branching between symmetric and nonsymmetric perimeter partitions is investigated. It is based on a certain convexity defect of an optimal value function. The perimeter partition problem is treated as a special case of partition problems for a certain class of convex-concave functions. MSC 1991: 52A40 (primary); 52A38, 90C90, 90C31 (secondary) Keywords: isoperimetric problem, global optimization, parametric optimization, convexity defect

1. Introduction

Our aim is to solve an isoperimetric partition problem for m-tuples of sector indomains having least area. We investigate its solution structure in dependence on the given parameter value. This problem was studied for m-tuples of unit circle indomains by März in [5]. Because of its hierarchic structure it is based on the generalized Favard problem (see [3]) and the partition problem for pairs of sector indomains (see [4]). Before formulating the optimization problem we summarize some basic definitions and notations. We denote by S_{ω} the unit circular sector with central angle ω ∈ [0, 2π], and by Δ_{ω} the corresponding isosceles triangle. Any closed plane set B with S_{ω} ∩ Δ_{ω} ⊆ B ⊆ S_{ω} and convex set Δ_{ω}∪B is called sector indomain of S_{ω}. The perimeter of the sector indomain B is composed by the legs of Δ_{ω} and a convex curve joining the free endpoints of these legs. This curve is the variable boundary part of domain B. We denote its length by L_{ω}(B), the area of B by F_{ω}(B). Now, the isoperimetric partition problem for m ω-sector indomains B_{1}, …, B_{m} can be formulated as follows:

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1998 Heldermann Verlag

(P) :  ∑_{i=1}^{m} F_{ω}(B_{i}) → Min!

∑_{i=1}^{m} L(B_{i}) = mΛ

with parameter Λ ∈ [\underline{L}_{ω}, ω], \underline{L}_{ω} = 2(k + sin \frac{ω̂}{2} ), ω̂ ∈ [0, π) and ω = kπ + ω̂ for k=1,2. For m = 1 (generalized Favard problem) it was shown [3] that a uniquely determined almost regular inpolyeder of S_{ω} is area-minimal. The number n of according central angles is given by L ∈ (l_{n−1}^{ω}, l_{n}^{ω}] with l_{1}^{ω} = \underline{L}_{ω} and

l_{n}^{ω} := 2n · sin \frac{ω}{2n} for n ≥ 2.  (1.1)

The minimal area depends parametrically on L. It is described by the piecewisely and implicitely given optimal value function (fonction penetrante)

f_{ω}(L) := \frac{n − 1}{2} sin α_{ω}(L) + \frac{1}{2} sin(ω − (n − 1)α_{ω}(L)).  (1.2)

In this, the central angle α_{ω}(L) is given by

L = 2(n − 1) sin \frac{α}{2} + 2 sin \frac{1}{2}(ω − (n − 1)α)  (1.3)

for L ∈ (l_{n−1}^{ω}, l_{n}^{ω}]. This function f_{ω} is a continuous and monotonously increasing function. It is piecewise continuously differentiable on (l_{n−1}^{ω}, l_{n}^{ω}) for n ≥ 2. For n ≥ 3 there exists a turning point ^{1}λ_{n}^{ω} ∈ (l_{n−1}^{ω}, l_{n}^{ω}) such that f_{ω} is strictly convex on [l_{n−1}^{ω}, λ_{n}^{ω}] and strictly concave on [λ_{n}^{ω}, l_{n}^{ω}]. On [l_{1}^{ω}, l_{2}^{ω}] the function f_{ω} is strictly convex. The derivatives f_{ω}^{(3)} and f_{ω}^{(4)} are negative on (l_{n−1}^{ω}, l_{n}^{ω}) for all n ≥ 3. The hierarchic structure of (P) and the solution of the generalized Favard problem lead to the equivalent perimeter partition problem

(^{m}P^{ω,Λ}) :  ∑_{i=1}^{m} f_{ω}(L_{i}) →Min!

∑_{i=1}^{m} L_{i} = m · Λ

\underline{L}_{ω} ≤ L_{1} ≤ ⋯ ≤ L_{m} ≤ ω.

An optimal solution exists and is denoted by (L_{1}^{∗}, …, L_{m}^{∗}).

For m = 2 (pair partition problem) a branching between symmetric (L_{1}^{∗} = L_{2}^{∗}) and certain nonsymmetric (L_{1}^{∗} = l_{n−1}^{ω} or L_{2}^{∗} = l_{n}^{ω}) solutions occurs (see [4]). The number n is fixed by the condition Λ ∈ (l_{n−1}^{ω}, l_{n}^{ω}]. Hence,

L_{i}^{∗} ∈ [l_{n−1}^{ω}, l_{n}^{ω}], i = 1, …, m  (1.4)

is a necessary condition for an optimal perimeter partition of problem (^{m}P^{ω,Λ}).

2. A general partition problem

Let a function f : [0, 1] → R^{1} be given with the following properties: (A1) f ∈ C^{2}(0, 1), (A2) there exists a unique turning point ξ_{1} ∈ (0, 1) such that f′′(x) > 0 for x ∈ (0, ξ_{1}),

f′′(x) < 0 for x ∈ (ξ_{1}, 1). Under these assumptions on f we study the following partition problem:

(^{m}Q^{c}) :  ^{m}F (^{m}x) = ∑_{i=1}^{m} f(x_{i}) →Min!

∑_{i=1}^{m} x_{i} = m · c

0 ≤ x_{1} ≤ ⋯ ≤ x_{m} ≤ 1

for c ∈ (0, 1), ^{m}x = (x_{1}, …, x_{m}) ∈ R^{m}. The feasible domain B_{m}(c) of this optimization problem is nonempty and compact. Optimal solutions exist.

2.1. Convexity defects. The solution of problem (^{m}Q^{c}) is closely related to the curvature behavior of f.

Definition 1. Let μ ∈ (0, 1). The function

μφ_{f}(x) := \{ \begin{matrix}(1 − μ)f(0) + μf(\frac{1}{μ}x) − f(x) & for x < μ \\ μf(1) + (1 − μ)f (\frac{x−μ}{1−μ}) − f(x) & for x ≥ μ \end{matrix}

is called μ-point convexity defect of f.

For a convex function all these defect functions are nonnegative.

Lemma 1. Let μ ∈ (0, 1) and f be a function with properties (A1), (A2). Then there exists a unique zero ξ(μ) ∈ (0, 1) of ^{μ}φ_{f} with ^{μ}φ_{f}(x) > 0 for x ∈ (0, ξ(μ)) and

a) ξ(μ) ∈ (μξ_{1}, μ) for ^{μ}φ_{f}(μ) ≤ 0,

b) ξ(μ) ∈ (μ, ξ_{1} + μ(1 − ξ_{1})) for ^{μ}φ_{f}(μ) > 0.

Proof. a) Let x ∈ (0, μ]. For x ∈ (0, μξ_{1}) we get ^{μ}φ′_{f}(x) > 0 because f′′(x) > 0 on (0, ξ_{1}) implies f′(\frac{1}{μ}x) > f′(x). Hence, ^{μ}φ_{f}(0) = 0 yields ^{μ}φ_{f}(x) > 0 for x ∈ (0, μξ_{1}).

For x ∈ (μξ_{1}, ξ_{1}) it holds ^{μ}φ′′_{f}(x) < 0 because of f′′(\frac{1}{μ}x) < 0 and f′′(x) > 0. This means that ^{μ}φ_{f} is strictly concave on (μξ_{1}, ξ_{1}). Let ^{μ}φ_{f}(μ) ≤ 0. For ξ_{1} > μ it follows the existence of a unique zero ξ(μ) ∈ (μξ_{1}, μ) of μφ_{f}, immediately. For ξ_{1} ≤ μ we use that ^{μ}φ′_{f}(x) < 0 on (ξ_{1}, μ) because of f′′(x) < 0 on (ξ_{1}, 1).

b) Let x ∈ [μ, 1). We consider the reflection g(y) = −f(1 − y). This function has the properties (A1), (A2), too. Let η_{1} = 1 − ξ_{1} denote the unique turning point of g. Considering the (1 − μ)-proportional convexity defect of g we get ^{1−μ}φ_{g}(y) = −^{μ}φ_{f}(x) for 1 − x = y ∈ (0, 1 − μ]. Let ^{μ}φ_{f}(μ) > 0. From ^{1−μ}φ_{g}(1 − μ) = −^{μ}φ_{f}(μ) < 0 and case a) it follows the existence of a unique zero of ^{1−μ}φ_{g} on ((1 − μ)η_{1}, 1 − η). Hence, the defect function ^{μ}φ_{f} has a unique zero on (μ, ξ_{1} + μ(1 − ξ_{1})). □

In the special case μ = \frac{1}{m} we denote this zero by ξ_{m} = ξ(\frac{1}{m}). For μ = \frac{1}{2}, the convexity defect of this kind was introduced by J. Focke [1]. We call it midpoint convexity defect.

2.2. Partition problem for pairs. We consider the partition problem (^{2}Q^{c}). An equivalent optimization problem is given by

(Q) :  F (x) := f(x) + f(2c − x) →Min!
x ∈ [0, 1] ∩ [2c − 1, 2c].

First, we study stationary points of the symmetric objective function F on the open interval (0, 1) ∩ (2c − 1, 2c).

Lemma 2. Let ξ_{1} be the unique turning point of f ∈ C^{2}(0, 1) with property (A2). Then 1) x = c is a local minimum of F on (0, 1) ∩ (2c − 1, 2c) if c < ξ_{1}, and a local maximum

if c > ξ_{1},

2) x = c is the only local minimum of F on (0, 1) ∩ (2c − 1, 2c) if f ∈ C^{4}(0, 1) and f^{(3)}(x) < 0,f^{(4)}(x) < 0 for all x ∈ (0, 1).

Proof. 1) The statement follows immediately from (A2).

2) We show that f′(x) − f′(2c − c) = 0 implies f′′(x) + f′′(2c − x) < 0 for x ∈ (0, c) if f^{(3)}(x) < 0, f^{(4)}(x) < 0 for x ∈ (0, 1). Because the local maximum ξ_{1} is the only stationary point of f′ on (0,1) a stationary point x ∈ (0, c) of F satisfies x < ξ_{1} < 2c − x. It can be shown (see [4]) that the function Q(x) := −2f′′′(ξ_{1})(f′(x) − f′(ξ_{1})) + f′′^{2}(x) is strictly monotonously increasing on (0, 1). This property yields the implication stated above. Hence, each stationary point x ∈ (0, c) is a maximal point. □

Lemma 2 gives a sufficient criterion for the following additional condition on f:

(A3) For c, x, 2c−x∈(0, 1), x≠c, relation f′(x)=f′(2c−x) implies f′′(x)+f′′(2c−x) < 0. Now, we investigate the solution behavior of problem (^{2}Q^{c}) in dependence on the parameter c where f fulfills the conditions (A1), (A2) and (A3).

Lemma 3. The zero ξ_{2} of the midpoint convexity defect ^{\frac{1}{2}} φ_{f} is a branch point for the solution structure of (^{2}Q^{c}) according to

1) ^{2}x = (c, c) is optimal for 0 < c ≤ ξ_{2},

2) ^{2}x = (0, 2c) is optimal for ξ_{2} ≤ c ≤ \frac{1}{2},

3) ^{2}x = (2c − 1, 1) is optimal for Max\{ξ_{2}, \frac{1}{2}\} ≤ c < 1. It holds the sharpened inclusion ξ_{2} ∈ (\frac{1}{2}ξ_{1}, ξ_{1}).

Proof. We consider the equivalent problem (Q). For μ = \frac{1}{2}, Lemma 1 implies the unique existence of ξ_{2} where ^{\frac{1}{2}} φ_{f}(c) < 0 for c ∈ (ξ_{2}, 1). The solution structure 1), 2) and 3) results from (A3) and Lemma 2. If ^{\frac{1}{2}} φ_{f}(\frac{1}{2}) ≤ 0 we get \frac{1}{2}ξ_{1} ≤ ξ_{2}, and if ^{\frac{1}{2}} φ_{f}(\frac{1}{2}) > 0 we get \frac{1}{2}ξ_{1} < \frac{1}{2} ≤ ξ_{2} from Lemma 1. Assuming that ξ_{1} < ξ_{2}. For c with ξ_{1} < c ≤ ξ_{2} it follows that x = c is a local maximum of F. On (0, 1) \ {c} a local minimum does not exist because of condition (A3). This means that F is monotonously increasing on [0, c] and monotonously decreasing on [c, 1]. Otherwise, ^{\frac{1}{2}} φ_{f}(c) > 0 implies F (c) < F (0) for c ≤ \frac{1}{2} and F (c) < F (1) for c ≥ \frac{1}{2}, resp. This contradiction completes the proof. □

2.3. Partition problem for m-tuples. In this section, we want to study the solution branching of the partition problem (^{m}Q^{c}) under the condition (A3) on f. We denoted by B_{m}(c) the feasible domain of this problem. In the following, we use the notations

mx^{σ} = (c, …, c) ∈ R^{m}

for the symmetric solution,

me_{i} = (0, …, 0, 1, 0, …, 0) ∈ R^{m}

for the i-th unit vector. An index set I_{k} = {i_{1}, …, i_{k}}, 1 ≤ i_{1} < ⋯ < i_{k} ≤ n, k = 2, …, m−1, is denoted as selection of size k. Let ^{m}x be a feasible solution of (^{m}Q^{c}). Then

mx_{I_{k}} = (x_{i_{1}}, …, x_{i_{k}})

denotes a k-dimensional partial solution of ^{m}x according to the selection I_{k}. This partial solution is a feasible solution of problem (^{k}Q^{c_{I_{k}}} ) for

c_{I_{k}} = \frac{1}{k} ∑_{i∈I_{k}} x_{i}.

The following necessary optimality conditions result from the hierarchic structure of (^{m}Q^{c}).

Lemma 4. If ^{m}x^{∗} is an optimal solution of problem (^{m}Q^{c}) then the following conditions hold:

(1*) For each selection I_{k}, k = 2, …, m − 1, ^{m}x_{I_{k}}^{∗} is an optimal solution of problem (^{k}Q^{c_{I_{k}}} ) with c_{I_{k}} = \frac{1}{k} ∑_{i∈I_{k}} x_{i}^{∗}.

(2*) If x_{i}^{∗}, x_{j}^{∗} ∈ (0, 1) for some i, j ∈ {1, …, m}, i < j, then x_{i}^{∗} = x_{j}^{∗} ∈ (0, ξ_{2}].

(3*) If x_{i}^{∗} = 0 for an i ∈ {1, …, m} then x_{j}^{∗} ∉ (0, 2ξ_{2}) for all j ∈ {1, …, m}.

(4*) If c < \frac{1}{m} and ^{m}x^{∗} ≠ ^{m}x^{σ} then ^{m}x∗ = mc ·^{m}e_{m}.

(5*) If c ≥ \frac{1}{m} and ^{m}x^{∗} ≠ ^{m}x^{σ} then x_{m}^{∗} = 1.

Proof. Because of

\begin{aligned}^{m}F (^{m}x^{∗}) & = ∑_{i∈I_{k}} f(x_{i}^{∗}) + ∑_{i∉I_{k}} f(x_{i}^{∗}) \\ & ≤ ∑_{i∈I_{k}} f(x_{i}) + ∑_{i∉I_{k}} f(x_{i}^{∗}) \end{aligned}

for all ^{m}x ∈ B_{m}(c) with ∑_{i∈I_{k}} x_{i} = k · c_{I_{k}} and x_{i} = x_{i}^{∗} for i ∉ I_{k} we get (1^{∗}). The partial solution ^{m}x_{I_{2}}^{∗} = (x_{i}^{∗}, x_{j}^{∗}) with I_{2} = (i, j) has to be an optimal solution of problem (^{2}Q^{c_{I_{2}}} ). This follows from (1^{∗}). Lemma 3 yields (2^{∗}) and (3^{∗}). If c < \frac{1}{m} then ∑_{i=1}^{m} x_{i}^{∗} < 1 and x_{i}^{∗} < 1 for all i. Because ^{m}x^{∗} ≠ ^{m}x^{σ} there exists any selection I_{2} = (r, s) with x_{r}^{∗} ≠ x_{s}^{∗}. Hence, it follows x_{r}^{∗} = 0 from (2^{∗}) and x_{j}^{∗} ∉ (0, 2ξ_{2}) for all j from (3^{∗}). Because of condition (2^{∗}) there is no pair (x_{i}^{∗}, x_{j}^{∗}) with x_{i}^{∗}, x_{j}^{∗} ∈ (0, 1). From x_{i}^{∗} < 1 for all i we get (4^{∗}). If c ≥ \frac{1}{m} then x_{m}^{∗} = 1. Assuming that x_{i}^{∗} < 1 for all i then the conditions (2^{∗}) and (3^{∗}) yield x_{m}^{∗} = mc which is a contradiction to x_{m}^{∗} < 1. □

To determine solutions of the partition problem we describe the subset of B_{m}(c) satisfying the necessary optimality conditions of Lemma 4. We denote this set by B_{m}^{∗}(c). The hierarchic structure of (^{m}Q^{c}) suggests to apply the method of complete induction. If we get just one element then we have found the global optimal solution ^{m}x^{∗}. In the other case we take a decision between the elements of B_{m}^{∗}(c) using the convexity defect of f.

Theorem 1. Let \{ξ_{k}\} be the sequence of zeroes defined by the \frac{1}{k} -point convexity defects \frac{1}{k} φ_{f} of f. Then these zeroes satisfy the recursive conditions

ξ_{k} ∈ (\frac{k − 1}{k}ξ_{k−1}, ξ_{k−1}) for k ≥ 2.

They define branch points \frac{1}{m} (k · ξ_{k} + m − k) for the solution structure of the partition problem (^{m}Q^{c}) in the following manner:

1. ^{m}x^{∗} = ^{m}x^{σ} for c ∈ [0, ξ_{m}],

2. ^{m}x^{∗} = (mc − j) ·^{m}e_{m−j} + ∑_{i=m−j+1}^{m} ^{m}e_{i} for c ∈ \frac{1}{m}[(m − j)ξ_{m−j} + j, j + 1], j ∈ \{0, …, m − 1\},

3. ^{m}x^{∗} = \frac{mc−j+1}{m−(j+1)} ∑_{i=1}^{m−(j+1)} ^{m}e_{i} + ∑_{i=m−j}^{m} ^{m}e_{i} for c ∈ \frac{1}{m}[Max\{(m−j)ξ_{m−j}+j, j+1\}, j+1+(m−(j+1))ξ_{m−(j+1)}], j ∈ \{0, …, m−2\}.

Proof. For m = 2 the assertion follows from Lemma 3. Let the assertion hold for all k ≤ m − 1, m > 2. Then

ξ_{i−1} > ξ_{i}, (i − 1)ξ_{i−1} < iξ_{i}  (2.1)

holds for i = 2, …, m − 1.

First step: We study the set B_{m}^{∗}(c) by distinguishing three cases for the parameter value. Case 1: c ∈ [0, ξ_{m−1}]. (2.1) implies c ∈ [0, ξ_{k}] for k = 1, …, m−1. Hence, ^{m}x^{σ} ∈ B_{m}^{∗}(c) by induction hypothesis. Case 1.1: c ∈ [0, \frac{m−1}{m}ξ_{m−1}). Let ^{m}x ∈ B_{m}^{∗}(c), and let I_{m−1} ⊆ {1, …, m} be an arbitrary selection of size m − 1. Then

c_{I_{m−1}} = \frac{1}{m − 1} ∑_{i∈I_{m−1}} x_{i} ≤ \frac{1}{m − 1} ∑_{i=1}^{m} x_{i} = \frac{m}{m − 1}c < ξ_{m−1},

and hence we get x_{i_{1}} = ⋯ = x_{i_{m−1}} by (1^{∗}) and induction hypothesis. This means that B_{m}^{∗}(c) = {^{m}x^{σ}}. Case 1.2: c ∈ [\frac{m−1}{m}ξ_{m−1}, ξ_{m−1}]. Let ^{m}x̂ ∈ B_{m}^{∗}(c) with ^{m}x̂ ≠ ^{m}x^{σ}. Case 1.2.1: c < \frac{1}{m}. The necessary optimality condition (4^{∗}) implies

B_{m}^{∗}(c) = {^{m}x^{σ}, ^{m}x̂} with ^{m}x̂ = mc ·^{m}e_{m}.

Case 1.2.2: c ≥ \frac{1}{m}. This case occurs only for ξ_{m−1} ≥ \frac{1}{m}. The necessary optimality condition (5^{∗}) implies x̂_{m} = 1. Because of ξ_{m−1} ∈ (0, 1) we get

∑_{i=1}^{m−1} x̂_{i} = mc − 1 ≤ mξ_{m−1} − 1 < (m − 1)ξ_{m−1}

and c_{I_{m−1}} = \frac{mc−1}{m−1} ∈ [0, ξ_{m−1}) for the selection I_{m−1} = \{1, …, m − 1\}. By induction hypothesis it follows x̂_{1} = ⋯ = x̂_{m−1} = c_{I_{m−1}} and

mx̂ = \frac{mc − 1}{m − 1} ∑_{i=1}^{m−1}^{m}e_{i} + 1^{m}e_{m}.

On the other hand, we apply (1^{∗}) and the induction hypothesis on ^{m}x̂_{I_{m−1}} for the selection I_{m−1} = \{2, …, m\} with c_{I_{m−1}} = \frac{(m−2)mc+1}{(m−1)^{2}}. From

(m − 1)c_{I_{m−1}} = ∑_{i=2}^{m} x_{i} < (m − 2)c + 1 ≤ (m − 2)ξ_{m−1} + 1

and condition (2.1) we get

(m − 1)c_{I_{m−1}} < (m − 2)ξ_{m−2} + 1.  (2.2)

By induction hypothesis and (1^{∗}), the structure of ^{m}x̂_{I_{m−1}} and (2.2) imply

c_{I_{m−1}} ∈ \frac{1}{m − 1} [Max\{(m − 1)ξ_{m−1}, 1\}, (m − 2)ξ_{m−2} + 1] .

Because of (2.2) and c ≥ \frac{1}{m} this condition is equivalent to

c ≥ \frac{(m − 1)^{2}ξ_{m−1} − 1}{m(m − 2)}.  (2.3)

Summarizing this case we get

B_{m}^{∗}(c) = \{ \begin{matrix}\{^{m}x^{σ}, ^{m}x̂\} & for c ≥ \frac{(m−1)^{2}ξ_{m−1}−1}{m(m−2)} \\ \{^{m}x^{σ}\} & else \end{matrix}

with ^{m}x̂ = \frac{mc−1}{m−1} ∑_{i=1}^{m−1} ^{m}e_{i} + 1^{m}e_{m}.

Case 2: c ∈ (ξ_{m−1}, \frac{1}{m}]. This case occurs for ξ_{m−1} < \frac{1}{m}, only. Let ^{m}x ∈ B_{m}^{∗}(c). Then ^{m}x ≠ ^{m}x^{σ} because the partial solution ^{m}x^{σ}_{I_{m−1}} with c_{I_{m−1}} = c > ξ_{m−1} does not satisfy (1^{∗}) and the induction hypothesis. From (4^{∗}) and (5^{∗}) it follows B_{m}^{∗}(c) = {mc ·^{m}e_{m}}.

Case 3: c ∈ (Max\{ξ_{m−1}, \frac{1}{m}\}, 1]. For ^{m}x ∈ B_{m}^{∗}(c) we have ^{m}x ≠ ^{m}x^{σ} like in Case 2. This implies x_{m} = 1 from (5^{∗}). We consider the selection I_{m−1} = \{1, …, m − 1\} with c_{Im−1} = \frac{mc−1}{m−1}. Then, the structure of mx_{I_{m−1}} results from the induction hypothesis.

Second step: In Case 1.2 it remains to compare the objective values of the two solutions coming into question as global optimal solutions. One of these solutions is the symmetric solution ^{m}x^{σ}. A decision is taken via the sign of the \frac{1}{m}-point convexity defect ^{\frac{1}{m}} φ_{f} of f. Because of Lemma 1 there exists a unique zero ξ_{m} ∈ (0, 1) of ^{\frac{1}{m}} φ_{f} with ^{\frac{1}{m}} φ_{f}(c) > 0 for c < ξ_{m}. This yields the global optimality of ^{m}x^{σ} for parameter values c ∈ [0, ξ_{m}]. It remains to show the recursive condition (2.1) for m, that is ξ_{m} ∈ (\frac{m−1}{m}ξ_{m−1}, ξ_{m−1}). For this we verify

\frac{1}{m} φ_{f} (\frac{m − 1}{m}ξ_{m−1}) > 0  (2.4)
\frac{1}{m} φ_{f} (ξ_{m−1}) < 0  (2.5)

Proof of (2.4): Case I: c = \frac{m−1}{m}ξ_{m−1} < \frac{1}{m}. According to Case 1.2.1 we have B_{m}^{∗}(c) = {^{m}x^{σ},^{m}x̂} with ^{m}x̂ = mc ·^{m}e_{m}. Considering the selection I_{m−1} = {2, …, m} we get the optimality of ^{m}x̂_{I_{m−1}} for problem (^{m−1}Q^{c_{I_{m−1}}} ) with c_{I_{m−1}} = ξ_{m−1} from the induction hypothesis. For this parameter value the point ^{m−1}x^{σ} is optimal, too. Hence ^{m}F (^{m}x̂) = ^{m}F (^{m}x̃) where ^{m}x̃ = ξ_{m−1} ∑_{i=2}^{m} ^{m}e_{i} and ^{m}x̃_{I_{m−1}} = ^{m−1}x^{σ}. But for the selection I_{m−1} = {1, …, m − 1} the partial solution mx̃_{I_{m−1}} is not optimal for problem (^{m−1}Qc̃_{I_{m−1}} ) because c̃_{I_{m−1}} < ξ_{m−1}. Therefore, neither mx̃ nor ^{m}x̂ are optimal solutions of (^{m}Q^{c}). This implies (2.4).

Case II: c = \frac{m−1}{m}ξ_{m−1} ≥ \frac{1}{m}.

According to Case 1.2.2, \frac{mc−1}{m−1} ∑_{i=1}^{m−1} ^{m}e_{i} + 1^{m}e_{m} ∈ B_{m}^{∗}(c) if c satisfies condition (2.3). But

(m − 1)(m − 2)ξ_{m−1} < (m − 1)(m − 2)ξ_{m−1} + (m − 1)ξ_{m−1} − 1

is equivalent to

c = \frac{m − 1}{m}ξ_{m−1} < \frac{(m − 1)^{2}ξ_{m−1} − 1}{m(m − 2)}

which implies B_{m}^{∗}(c) = \{^{m}x^{σ}\}. We get ^{\frac{1}{m}} φ_{f}(\frac{m−1}{m}ξ_{m−1}) > 0. Relation (2.4) is shown.

Proof of (2.5): Case III: c = ξ_{m−1} < \frac{1}{m}. From Case 1.2.1 we have B_{m}^{∗}(c) = {^{m}x^{σ},^{m}x̂} with ^{m}x̂ = mξ_{m−1}^{m}e_{m}. Because of the induction hypothesis ^{m}x_{I_{m−1}}^{σ} = ^{m−1}x^{σ} and ^{m−1}x̂ = (m − 1)ξ_{m−1}^{m−1}e_{m−1} are optimal solutions of problem (^{m−1}Q^{c_{I_{m−1}}} ) with c_{I_{m−1}} = ξ_{m−1}. Hence ^{m}F (^{m}x^{σ}) = ^{m}F (^{m}x̃) holds for ^{m}x̃ = ξ_{m−1} ·^{m}e_{m−1} + (m − 1)ξ_{m−1} ·^{m}e_{m}. The selection I_{2} = {m − 1, m} generates the partial solution ^{m}x̃_{I_{2}} with c_{I_{2}} = \frac{m}{2}ξ_{m−1} ∈ (ξ_{2}, \frac{1}{2}). Lemma 3 implies that ^{m}x̃_{I_{2}} is not an optimal solution for (^{2}Q^{c_{I_{2}}} ) but ^{2}x̂ = mξ_{m−1}^{2}e_{2}. From ^{m}x̂_{I_{2}} = ^{2}x̂ it follows mF (^{m}x^{σ}) = ^{m}F (^{m}x̃) > ^{m}F (^{m}x̂) and therefore (2.5).

Case IV: c = ξ_{m−1} ≥ \frac{1}{m}.

This parameter value satisfies relation (2.3) in Case 1.2.2. Hence B_{m}^{∗}(c) = {^{m}x^{σ},^{m}x̂} with ^{m}x̂ = \frac{mc−1}{m−1} ∑_{i=1}^{m−1} ^{m}e_{i} + 1^{m}e_{m}. If ξ_{m−1} ≥ \frac{1}{m−1} then by induction hypothesis both m−1x_{I_{m−1}}^{σ} = ^{m−1}x^{σ} and ^{m−1}x̂ = \frac{(m−1)ξ_{m−1}−1}{m−2} ∑_{i=1}^{m−2} ^{m−1}e_{i} + 1 ·^{m−1} e_{m−1} are optimal solutions of problem (^{m−1}Q^{c_{I_{m−1}}} ) with c_{I_{m−1}} = ξ_{m−1}. This implies ^{m}F (^{m}x^{σ}) = ^{m}F (^{m}x̃) with

mx̃ = \frac{(m − 1)ξ_{m−1} − 1}{m − 2} ∑_{i=1}^{m−2}^{m}e_{i} + ξ_{m−1} ·^{m}e_{m−1} + 1 ·^{m}e_{m}.

Considering the selection I_{m−1} = {1, …, m − 1} the partial solution ^{m}x̂_{I_{m−1}} = ^{m−1}x^{σ} with c_{I_{m−1}} = \frac{1}{m−1}(mξ_{m−1} − 1) < ξ_{m−1} is the only optimal one for problem (^{m−1}Q^{c_{I_{m−1}}} ). Hence ^{m}F (^{m}x^{σ}) = ^{m}F (^{m}x̃) > ^{m}F (^{m}x̂) implies (2.5). If ξ_{m−1} < \frac{1}{m−1} then the induction hypothesis yields the global optimality of ^{m}x_{I_{m−1}}^{σ} and ^{m−1}x̂ = (m − 1)ξ_{m−1}^{m−1}e_{m−1} for problem (^{m−1}Q^{c_{I_{m−1}}} ) with c_{I_{m−1}} = ξ_{m−1}. From this we get ^{m}F (^{m}x^{σ}) = ^{m}F (^{m}x̃) with mx̃ = ξ_{m−1}^{m}e_{m−1} + (m − 1)ξ_{m−1}^{m}e_{m}. With respect to ^{m}x̃ the selection I_{2} = {m − 1, m} leads to problem (^{2}Q^{c_{I_{m−1}}} ) with c_{I_{2}} = \frac{m}{2}ξ_{m−1} ∈ [Max\{ξ_{2}, \frac{1}{2}\}, 1). Lemma 3 gives the optimal solution ^{2}x̂ = (mξ_{m−1} − 1)^{2}e_{1} + 1 ·^{2}e_{2} differing from ^{m}x̃_{I_{2}}. According to ^{m}x̄ = (mξ_{m−1}−1)^{m}e_{m−1}+1·^{m}e_{m} with^{m}x̄_{I_{2}} = ^{2}x̂ we consider the selection I_{m−1} = {1, …, m−1} where c_{I_{m−1}} = \frac{1}{m−1}(mξ_{m−1} − 1) < ξ_{m−1}. Then ^{m−1}x^{σ} is the optimal solution for problem (^{m−1}Q^{c_{I_{m−1}}} ). Because of^{m}x̂_{I_{m−1}} = ^{m−1}x^{σ} we finally get^{m}F (^{m}x^{σ}) = ^{m}F (^{m}x̃) > ^{m}F (^{m}x̂). Relation (2.5) is shown.

Third step: Collecting the results we verify the solution structure for problem (^{m}Q^{c}) in dependence on the parameter value. For c ∈ [0, ξ_{m}] the global optimal solution is given by ^{m}x^{σ}. This yields point 1 of the assertion. For c ∈ [ξ_{m}, \frac{1}{m}], ^{m}x̂ = mc ·^{m}e_{m} is optimal which corresponds to point 2 with j = 0 of the assertion. For c ∈ [Max\{ξ_{m}, \frac{1}{m}\}, ξ_{m−1}] the point ^{m}x̂ = \frac{mc−1}{m−1} ∑_{i=1}^{m−1} ^{m}e_{i} + 1 ·^{m}e_{m} is optimal. This is one part of point 3, j = 0 of the assertion. For c ∈ [Max\{ξ_{m−1}, \frac{1}{m}\}, 1] we consider case 3. We have found x_{m} = 1 for the optimal solution^{m}x̂ ≠ ^{m}x^{σ}. Hence, choosing the selection I_{m−1} = {1, …, m−1} the point^{m}x̂_{I_{m−1}} with corresponding

c_{I_{m−1}} = \frac{mc − 1}{m − 1} ∈ \frac{1}{m − 1} (Max\{mξ_{m−1} − 1, 0\}, m − 1]  (2.6)

is determined by the induction hypothesis. The zero ξ_{m−1} belongs to the interval used in (2.6), too. All different cases for c_{I_{m−1}} result in conditions on the parameter c and in structural statements on the (k − 1)-dimensional partial solution ^{m}x̂_{I_{m−1}}. Especially, the case c_{I_{m−1}} ≤ ξ_{m−1} yields the remaining part of point 3, j = 0 of the assertion. This completes the proof. □

The points \frac{1}{m}((m − j)ξ_{m−j} + j), j ∈ \{0, …, m − 1\}, are branch points for the solution structure. Two different solution structures correspond to these parameter values. For the remaining parameter values the solution is uniquely determined.

3. The m-sector problem

The m-sector problem led to the perimeter partition problem (^{m}P^{ω,Λ}). For its solution we use the results of the previous section.

3.1. General solution. Let n be determined from Λ ∈ (l_{n−1}^{ω}, l_{n}^{ω}]. Because of (1.4) we can transform problem (^{m}P^{ω,Λ}) by

L(x) = l_{n−1}^{ω} + x(l_{n}^{ω} − l_{n−1}^{ω}), x ∈ [0, 1]  (3.1)

into a general partition problem (^{m}Q^{c}). In this we have f(x) = f_{ω}(L(x)), L_{i} = L(x_{i}), L(c) = Λ where condition (A3) is valid. The solution structure of the m-sector-problem follows from Theorem 1. For ^{k}λ_{n}^{ω} = L(ξ_{k}) we get the recursive conditions

kλ_{n}^{ω} ∈ (\frac{k − 1}{k} ·^{k−1}λ_{n}^{ω} + \frac{1}{k} l_{n−1}^{ω},^{k−1}λ_{n}^{ω}) .  (3.2)

The optimal solution ^{m}L^{∗} = (L_{1}^{∗}, …, L_{m}^{∗}) of problem (^{m}P^{ω,λ}), m ≥ 2, is given via (3.1) by 1.

mL^{∗} = (Λ, …, Λ)  (3.3)
for  Λ ∈ [l_{n−1}^{ω}, ^{m}λ_{n}^{ω}],  (3.4)

2.

mL^{∗} = \underbrace{(l_{n−1}^{ω}, …, l_{n−1}^{ω}}_{m−(j+1)}, mΛ − jl_{n}^{ω} − (m − j − 1)l_{n−1}^{ω}, \underbrace{l_{n}^{ω}, …, l_{n}^{ω}}_{j})  (3.5)

for  Λ ∈ \frac{1}{m}[(m − j) ·^{m−j}λ_{n}^{ω} + jl_{n}^{ω}, (m − (j + 1))l_{n−1}^{ω} + (j + 1)l_{n}^{ω}]  (3.6)
and for j ∈ {0, …, m − 1},

3.

mL^{∗} = (\frac{mΛ − (j + 1)l_{n}^{ω}}{m − (j + 1)} , …, \frac{mΛ − (j + 1)l_{n}^{ω}}{m − (j + 1)} , \underbrace{l_{n}^{ω}, …, l_{n}^{ω}}_{j+1})  (3.7)

for Λ ∈\frac{1}{m}[Max\{(m − j) ·^{m−j}λ_{n}^{ω} + jl_{n}^{ω}, (m − (j + 1))l_{n−1}^{ω} + (j + 1)l_{n}^{ω}\},
(j + 1)l_{n}^{ω} + (m − (j + 1)) ·^{m−(j+1)}λ_{n}^{ω}]  (3.8)
and for j ∈ {0, …, m − 2}.

A parameter interval (3.6) could be empty. But for fixed m and large n we get the asymptotical statement

\frac{^{k}λ_{n}^{ω} − l_{n−1}^{ω}}{l_{n}^{ω} − l_{n−1}^{ω}} ≤ \frac{1}{k} for n ≥ n_{0}(k)

from the asymptotical behavior of ^{2}λ_{n}^{ω} (see [4]) and condition (3.2). Hence, all parameter intervals are empty for sufficiently large n.

3.2. Numerical treatment. For computing the branch points ^{k}λ_{n}^{ω}, k = 1, …, m, the Newton method is used and implemented in a Pascal program (see [1]). Numerical results are demonstrated in Table 1 for circles and circular sectors.

n  λ_{n}^{ω}  ^{2}λ_{n}^{ω}  ^{3}λ_{n}^{ω}
ω = 2π 3 4,841229182759 4.781149802531 4,705506391993
4 5,443310539518 5,418303371589 5,364902005334
5 5,749730218646 5,744385342917 5,720909572668
6 5,919419588012 5.917855737553 5,907410698360
8 6,086130367576 6.085898726378 6,082953567423
10 6,160823528643 6.160769675755 6,159653317247
30 6,270946658417 6,270946606643 6,270935708359
ω = \frac{π}{3}  3 1,040688511114 1.040450413358 1,040192062429
4 1,043274926103 1.043114785701 1,042914996012
5 1,044695465118 1.044661940328 1,044538632024
6 1,045493875409 1.045485013601 1,045432384556
8 1,046278280656 1.046277086069 1,046262813669
10 1,046628166088 1.046627899577 1,046622582538
30 1,047140858911 1,047140858072 1,047140807906

Table 1

For three circles and n = 4 we get four different partition qualities (see Fig. 1). The solution structure of type (3.5) with j = 0 does not come into question. This results from

\frac{2}{3} l_{3}^{ω} + \frac{1}{3} l_{4}^{ω} = 5, 34972 < 5, 36490 = ^{3}λ_{4}^{ω},
\frac{1}{3} l_{3}^{ω} + \frac{2}{3} l_{4}^{ω} = 5, 50329 > 5, 49782 = \frac{2}{3} ^{2}λ_{4}^{4} + \frac{1}{3} l_{4}^{ω}.

The other intervals are nonempty.

For three circular sectors with n = 3 and ω = \frac{π}{3} we have

\frac{2}{3} l_{2}^{ω} + \frac{1}{3} l_{3}^{ω} = 1, 03748 < 1, 04019 = ^{3}λ_{3}^{ω},
\frac{1}{3} l_{2}^{ω} + \frac{2}{3} l_{3}^{ω} = 1, 03968 < 1, 04093 = \frac{2}{3} ^{2}λ_{3}^{ω} + \frac{1}{3} l_{3}^{ω}.

This implies that the intervals of type (3.5) with j = 0 and j = 1 are empty. Only three different solution structures occur.

Figure 1

References

[1] Bröcker, C.: Über ein ungeklärtes Optimierungsproblem zu ebenen konvexen Bereichen. Diplomarbeit, Universität Leipzig 1990.

[2] Focke, J.; Klötzler, R.: Flächenminimale Paare von Inpolygonen des Einheitskreises. Manuskripte 1989.

[3] Kripfganz, A.: The Generalized Favard Problem. Beiträge Algebra Geom. 36 (1995) (2), 185–202.

[4] Kripfganz, A.: An Isoperimetric Partition Problem. Beiträge Algebra Geom. 38 (1997) (1), 161–181.

[5] März, Ch.: Ein Optimierungsproblem zu Favard’s ’fonction penetrante’. Diplomarbeit, Universität Leipzig 1990.

Received January 11, 1997, revised version December 11, 1997