Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 38 (1997), No. 1, 161-181.

An Isoperimetric Partition Problem

Anita Kripfganz

Institut für Mathematik, Universität Leipzig, Augustusplatz 10, 04109 Leipzig, Germany

Abstract. In the present paper pairs of plane figures are considered. Each of them is inscribed into a unit circular sector with the same central angle. These indomains are linked together by the fixed total perimeter length. Pairs of figures with minimal total area and the corresponding partition of the total perimeter are determined. In general, the solution is not symmetrical. The basis for this problem forms the generalized Favard problem [6] and the analytical properties of its optimal value function.

1. Introduction

In the first half of this century one tried to find optimal parameters of convex figures while fixing other parameters. For a large number of problems this was done successfully using problem-specific methods [2]. Investigating such geometrical extremal problems we have met the isoperimetric partition problem presented in this paper. The generalized Favard problem published recently in ref. [6] forms the basis for its solution. It deals with the search for a plane figure of fixed perimeter length, inscribed into a circular sector and having minimal area. We denote by S_{ω} the circular sector with radius 1 and angle ω ∈ [0, 2π]. Let Δ_{ω} be the corresponding isosceles triangle.

Definition 1. Any closed plain set B with S_{ω} ∩ Δ_{ω} ⊆ B ⊆ S_{ω} and Δ_{ω} ∪ B convex is called ω-sector indomain of S_{ω}.

In this paper we consider a pair of plain domains, each inscribed into a unit circular sector S_{ω}. We pose the following question:

What is the pair of ω-sector indomains with fixed total perimeter length, having minimal total area?

For a pair of unit circle indomains this problem was formulated and investigated by J. Focke and R. Klötzler [5] from 1987 to 1989. Generalizations for sector indomains were studied by A. Brach [1].

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

This extremal problem shows a hierarchic structure. It can be divided into two generalized Favard problems if we parametrically fix the perimeter length of each sector indomain. Through the given total perimeter length these two problems are linked together. We know the solutions of the partial problems. The corresponding optimal value function is the so-called fonction penetrante. Using these informations we determine minimizers over disjunct parts of the feasible domain. A certain convexity defect of the fonction penetrante involves a structural branching of the global minimal solution in dependence on the total perimeter length.

For some parameter values we demonstrate the solution and its branching by numerical calculations.

2. General Basic Problem

In ref. [6] we have shown that the solution of the generalized Favard problem is polyhedral. The boundary of a polyhedral sector indomain is composed by the legs of Δ_{ω} and a polygon p_{ω}.

Definition 2. A polyhedral ω-sector indomain P_{ω} is called ω-inpolyeder of S_{ω} if all vertices of P_{ω} except the vertex of S_{ω} belong to the sector arc. The corresponding polygon p_{ω} is called ω-inpolygon of S_{ω}.

Because we seek the solution of the generalized Favard problem among ω-inpolyeders this problem was reduced to the following basic problem:

(P^{ω,L}) :  F_{ω}(φ, n) : = \frac{1}{2} ∑_{i=1}^{n} sin φ_{i} → Min!

L_{ω}(φ, n) : = 2 ∑_{i=1}^{n} sin \frac{φ_{i}}{2} = L

∑_{i=1}^{n} φ_{i} = ω
0 < φ_{i} ≤ π for i = 1, ..., n

In this, the central angles φ_{i} describe the inpolygon p_{ω}. For the inpolyeder P_{ω} we use the representation

P_{ω} = [φ_{1}, ..., φ_{n}].

The corresponding inpolygon p_{ω} represents the variable part of its perimeter. We call it p-perimeter and denote its length by L(P_{ω}) and the area of P_{ω} by F(P_{ω}), where L(P_{ω}) = L_{ω}(φ, n) and F(P_{ω}) = F_{ω}(φ, n). It is useful to regard this problem for all ω ≥ 0. This means considering multiple embraced inpolygons. For this, we have added the upper bound π for φ_{i}. In ref. [6] it was shown that optimal solutions of the generalized Favard problem (ω ∈ (0, 2π]) fulfil this condition automatically. The minimal objective function value depends on the parameters L and ω. The lower bound of L is fixed by

\underline{L}_{ω} := 2 (k + sin \frac{ω̂}{2} )  (2.1)

where k is a non-negative integer and ω̂ ∈ [0, π) the angle according ω = kπ + ω̂. To describe optimal solutions we give the following definition.

Definition 3. An inpolygon p_{ω} of S_{ω} is called almost regular if all but one side of p_{ω} are equal, the remaining one is not greater than the others. The ω-inpolygon is called regular if all sides are equal. The corresponding inpolyeder P_{ω} is called almost regular and regular, resp.

A regular n-sided (n ≥ 2) inpolygon p_{n}^{ω} and the corresponding regular inpolyeder P_{n}^{ω} are described by the n equal central angles

α_{n}^{ω} := \{ \begin{matrix}Min \{ω, π\} & for n = 1 \\ \frac{ω}{n} & for n ≥ 2. \end{matrix}  (2.2)

The length of its p-perimeter is given by

l_{n}^{ω} := \{ \begin{matrix}\underline{L}_{ω} & for n = 1 \\ 2n sin \frac{ω}{2n} & for n ≥ 2. \end{matrix}  (2.3)

The case n = 1 corresponds to an ω-inpolygon of smallest length. An almost regular n-sided ω-inpolyeder is described by n − 1 equal central angles α and one defect angle δ = ω − (n − 1)α with 0 < δ ≤ α. Almost regular and regular inpolyeders of S_{ω} are optimal figures of the generalized Favard problem for L ∈ [\underline{L}_{ω}, ω).

Theorem 1. Problem (P^{ω,L}) is uniquely solvable for each ω ≥ 0 and L ∈ [\underline{L}_{ω}, ω] where a) the number n of central angles is determined by the relation

L ∈ (l_{n−1}^{ω}, l_{n}^{ω}] ,

b) the optimal central angles are determined by a unique angle α_{ω}(L) ∈ [α_{n}^{ω}, α_{n−1}^{ω}) according to

\begin{aligned}0 < φ_{1} & = ... = φ_{n} = α_{ω}(L) < π, \\ 0 < φ_{n} & = δ_{ω}(L) = ω − (n − 1)α_{ω}(L) ≤ α_{ω}(L). \end{aligned}

Sketch of the proof. The existence of the solution results from that of the geometrical extremal problem.

For ω ∈ (0, 2π] and restrictions φ_{i} ≤ ω instead of φ_{i} ≤ π we sketch the proof of ref. [6] in step 1 and step 2.

Step 1: We fix the optimal yet unknown number n and evaluate necessary and sufficient optimality conditions for the optimization problem (P^{ω,L}). We get

α := φ_{1} = ... = φ_{n−1} ≥ φ_{n} = ω − (n − 1)α =: δ > 0  (2.4)

as structural statement about the optimal solution.

Step 2: We verify the isoperimetric condition for L > \underline{L}_{ω}. For this purpose we consider the piecewise composed function

l_{ω}(α) = {^{j}l_{ω}(α) for α ∈ [α_{j}^{ω}, α_{j−1}^{ω}] , j = 2, 3, ...  (2.5)

with α_{j}^{ω} from (2.2) and

jl_{ω}(α) = 2(j − 1) sin \frac{α}{2} + 2 sin \frac{δ}{2}.  (2.6)

Then, we have to solve the nonlinear equation

L = l_{ω}(α)  (2.7)

for

α ∈ ∪_{j=2}^{∞} [α_{j}^{ω}, α_{j−1}^{ω}) = (0, Min {ω, π}).  (2.8)

Because the function l_{ω} is a strictly monotonously decreasing function of α, equation (2.7) has a unique solution α = α_{ω}(L) ∈ (0, Min{ω, π}). In dependence on L, α_{ω} is a strictly monotonously decreasing function, too. From (2.8) we get a unique number n with α ∈ [α_{n}^{ω}, α_{n−1}^{ω}). This relation corresponds via (2.7) and l_{n}^{ω} = l_{ω}(α_{n}^{ω}) to

L ∈ (l_{n−1}^{ω}, l_{n}^{ω}] .  (2.9)

Step 3: For ω > 2π and L > \underline{L}_{ω} there are at least two central angles of the optimal ω-inpolyeder P_{ω} smaller than π, say φ_{1}, φ_{2} < π. We assume that in the optimal solution of (P^{ω,L}) occurs one central angle π, say φ_{3} = π. Then, we consider the partial sector Sω̃ with ω̃ = φ_{1} + φ_{2} + φ_{3}. The partial inpolyeder Pω̃ with L(Pω̃) = L̃ = 2 ∑_{i=1}^{3} sin \frac{φ_{i}}{2} has to be area-minimal. Let

ϕ(φ, λ) = λ_{0} · \frac{1}{2} ∑_{i=1}^{3} sin φ_{i} + λ_{1} (2 ∑_{i=1}^{3} sin \frac{φ_{1}}{2} − L̃)

+ λ_{2} (∑_{i=1}^{3} φ_{i} − ω̃) + λ_{3}(φ_{3} − π)

be the Lagrangian function for (P^{ω̃,L̃}). The gradients (cos \frac{φ_{1}}{2} , cos \frac{φ_{2}}{2} , 0)^{T} and (1, 1, 1)^{T} of the constrained functions at φ = (φ_{1}, φ_{2}, π) are linearly independent. Therefore, there exist Lagrangian multipliers λ_{i} with λ_{3} ≥ 0, λ_{0} = 1 and ϕ_{φ}(φ, λ) = 0 (see [4]). This implies

λ_{1} = − (cos \frac{φ_{1}}{2} + cos \frac{φ_{2}}{2} )

λ_{2} = \frac{1}{2} + cos \frac{φ_{1}}{2} cos \frac{φ_{2}}{2}

and from φ_{3} = π

λ_{3} = \frac{1}{2} − λ_{2} = − cos \frac{φ_{1}}{2} cos \frac{φ_{2}}{2} < 0

in contradiction to λ_{3} ≥ 0. This means that all angles φ_{i} are less than π. Now, we can proceed as in step 1 and step 2. We return to ω ∈ [0, 2π]. In the following we use the notations I_{n} := [l_{n−1}^{ω}, l_{n}^{ω}] and I_{n}^{0} := (l_{n−1}^{ω}, l_{n}^{ω}).

Corollary 1. For any given parameter L ∈ (l_{n−1}^{ω}, l_{n}^{ω}] there exists one and only one almost regular inpolyeder of S_{ω} with p-perimeter length L. This one has n central angles and solves the general basic problem.

Proof. The assertion follows from Theorem 1. The isoperimetric condition in the shape of formula (2.7) is written for almost regular and regular inpolyeders, resp. It is uniquely solvable for an α ∈ [α_{n}^{ω}, α_{n−1}^{ω}) representing the solution of the general basic problem. The area of an almost regular inpolyeder depends on L. This functional connection can be described implicitely by means of

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

with δ_{ω}(L) = ω − (n − 1)α_{ω}(L) and α_{ω}(L) from

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

for L ∈ (l_{n−1}^{ω}, l_{n}^{ω}].The function f_{ω} is the optimal value function of problem (P^{ω,L}) and called fonction penetrante. We summarize some properties of f_{ω} [7].

Lemma 1. The function f_{ω} : [\underline{L}_{ω}, ω] → R is

a) continuous and strictly monotonously increasing,

b) strictly convex on [l_{1}^{ω}, l_{2}^{ω}], and for n ≥ 3 there exists one turning point λ_{n}^{ω} ∈ (l_{n−1}^{ω}, l_{n}^{ω}) such that f_{ω} is strictly convex on [l_{n−1}^{ω}, λ_{n}^{ω}] and strictly concave on [λ_{n}^{ω}, l_{n}^{ω}].

The proof of this lemma follows from sign properties of the first three derivatives of f_{ω} calculated by implicit differentiation [1] and summarized in the following lemma.

Lemma 2. The function f_{ω} is continuously differentiable on each interval I_{n}^{0} where

a) f′_{ω} > 0 and strictly concave on I_{n}^{0},

f′′_{ω} has a unique zero λ_{n}^{ω} on I_{n}^{0},

f′′′_{ω} < 0 and f_{ω}^{(4)} < 0 on I_{n}^{0} for all n ≥ 3,

b) f′_{ω} > 0 and linear on I_{2}^{0}, f′′ > 0 on I_{2}^{0}.

Further we use that any almost regular inpolyeder is decomposable in a regular and an almost regular inpolyeder. This is carried over to the corresponding p-perimeters.

Lemma 3. The p-perimeter of an almost regular inpolyeder satisfies the decomposition rule

l_{k·α+ω}(α) = l_{k·α}(α) + l_{ω}(α).

Proof. Let ω′ = k · α + ω. P_{ω′} is the almost regular inpolyeder of S_{ω′} with p-perimeter L(P_{ω′}) = L′ = l_{ω′}(α). The parameter L′ corresponds uniquely to the angle α. This implies ω′ = k′ · α + δ with k′ > k and ω = (k′ − k) · α + δ for any 0 < δ ≤ α. From (2.5) and (2.6) follows the decomposition rule. Furthermore, there are two possibilities for composing a regular (n−1)-sided and an almost regular n-sided inpolyeder.

Lemma 4. Let P_{2ω} be composed of a regular (n−1)-sided ω-inpolyeder P_{ω,1} and an almost regular n-sided ω-inpolyeder P_{ω,2}. Then, the p-perimeter of P_{2ω} satisfies the composition rule

L(P_{2ω}) = l_{ω}(α) + l_{ω}(α_{n−1}^{ω}) = l_{(n−1)α}(α) + l_{ω+δ}(α_{n−1}^{ω})

for α ∈ [α_{n}^{ω}, α_{n−1}^{ω}), δ = ω − (n − 1)α.

Proof. Because P_{ω,1} is a regular (n − 1)-sided ω-inpolyeder its p-perimeter is given by L(P_{ω,1}) = l_{ω}(α_{n−1}^{ω}). The p-perimeter of the n-sided almost regular inpolyeder P_{ω,2} is given by L(P_{ω,2}) = l_{ω}(α) with a unique α ∈ [α_{n}^{ω}, α_{n−1}^{ω}). This yields

L(P_{2ω}) = l_{ω}(α) + l_{ω}(α_{n−1}^{ω})

where ω = (n−1)α+δ = (n−1)·α_{n−1}^{ω}. The composed inpolyeder P_{2ω} has the representation

P_{2ω} = [ \underbrace{α, ..., α}_{n−1}, δ, \underbrace{α_{n−1}^{ω}, ..., α_{n−1}^{ω}}_{n−1} ].

On the other hand, for ω′ = (n − 1)α we understand P_{2ω} as the composition of a regular (n−1)-sided ω′-inpolyeder P_{(n−1)·α} and an almost regular n-sided (ω+δ)-inpolyeder P_{ω+δ}. The p-perimeter of P_{2ω} remains unchanged and can be represented via (2.5) and (2.6) by

L(P_{2ω}) = l_{(n−1)α}(α) + l_{ω+δ}(α_{n−1}^{ω}).

3. Partition Problem

Now, we ask for an area-minimal pair of ω-sector indomains where the total perimeter length is fixed. For each feasible decomposition of the total perimeter length, both ω-sector indomains have to be optimal solutions of a generalized Favard problem. This means that only pairs (P_{ω,1}, P_{ω,2}) of almost regular ω-inpolyeders are under consideration as optimal solutions. These inpolyeders are linked through the total perimeter. Using the fonction penetrante to describe the area of P_{ω,i} (i = 1, 2) in dependence upon the p-perimeters L_{i} = L(P_{ω,i}) we get the following equivalent formulation of the partition problem:

(^{2}P^{ω,Λ})  ^{2}f_{ω}(L_{1}, L_{2}) : = f_{ω}(L_{1}) + f_{ω}(L_{2}) → Min!_{L_{1},L_{2}}
L_{1} + L_{2} = 2Λ
\underline{L}_{ω} ≤ L_{1} ≤ L_{2} ≤ ω

where the parameter Λ ∈ [\underline{L}_{ω}, ω] is chosen in advance. The symmetry of ^{2}f_{ω} with respect to l_{1} = l_{2} justifies the condition L_{1} ≤ L_{2}. A feasible solution is given by the symmetric pair (Λ, Λ). Optimal solutions of this nonlinear parametric problem exist because the objective function ^{2}f_{ω} is continuous and the feasible domain is nonempty and compact. To solve this problem we distinguish two cases with respect to the partition of the total length 2Λ onto L_{1} and L_{2}. For this, we fix n ≥ 2 according Λ ∈ (l_{n−1}^{ω}, l_{n}^{ω}] with l_{n}^{ω} from (2.3) and investigate

Case 1: L_{1}, L_{2} ∈ I_{n}^{0}, Case 2: L_{1} ≤ l_{n−1}^{ω} or L_{2} ≥ l_{n}^{ω}.

The cases L_{1} > l_{n}^{ω} and L_{2} ≤ l_{n−1}^{ω} cannot occur because we have L_{1} ≤ L_{2} and \frac{1}{2}(L_{1} +L_{2}) = Λ ∈ (l_{n−1}^{ω}, l_{n}^{ω}]. The second case can be formulated somewhat sharper by using the implications

Λ ∈ (l_{n−1}^{ω}, \frac{1}{2}(l_{n−1}^{ω} + l_{n}^{ω})] , L_{2} ≥ l_{n}^{ω} ⇒ L_{1} ≤ l_{n−1}^{ω}  (3.1)

and

Λ ∈ (\frac{1}{2}(l_{n−1}^{ω} + l_{n}^{ω}), l_{n}^{ω}] , L_{1} ≤ l_{n−1}^{ω} ⇒ L_{2} ≥ l_{n}^{ω}.  (3.2)

We get the subcases

Case 2.1: Λ ∈ (\frac{1}{2}(l_{n−1}^{ω} + l_{n}^{ω}), l_{n}^{ω}] =: I_{n}^{+}, L_{2} ≥ l_{n}^{ω}

Case 2.2: Λ ∈ (l_{n−1}^{ω}, \frac{1}{2}(l_{n−1}^{ω} + l_{n}^{ω})] =: I_{n}^{−}, L_{1} ≤ l_{n−1}^{ω}.

3.1. Almost Regular Twin Solutions

We consider Case 1: L_{1}, L_{2} ∈ I_{n}^{0}, and study necessary optimality conditions for problem (^{2}P^{ω,Λ}). Replacing L_{1} by L this problem is equivalent to the problem

(Q_{0}^{ω,Λ}) :  ^{2}f_{ω}(L, 2Λ − L) = f_{ω}(L) + f_{ω}(2Λ − L) → Min!
L ∈ I_{n}^{0} ∩ (2Λ − l_{n}^{ω}, Λ]

Solutions of (Q_{0}^{ω,Λ}) correspond to local minimizers of (^{2}P^{ω,Λ}) on I_{n}^{0} × I_{n}^{0}.

Theorem 2. If l_{n−1}^{ω} < L < 2Λ − L < l_{n}^{ω} then L is not a local minimal solution of problem (Q_{0}^{ω,Λ}).

Proof. At first, we consider the general case n ≥ 3. We use the Lagrangian method and prove that there is no feasible L ∈ I_{n}^{0} ∩ (2Λ − l_{n}^{ω}, Λ) satisfying the necessary optimality conditions

f′_{ω}(L) − f′_{ω}(2Λ − L) = 0,  (3.3)
f′′_{ω}(L) + f′′_{ω}(2Λ − L) ≥ 0.  (3.4)

Because f′_{ω} is strictly concave on I_{n}^{0} with the unique maximal point λ_{n}^{ω} ∈ I_{n}^{0} (see Lemma 1) we have L < λ_{n}^{ω} < 2Λ − L from (3.3). For such L we show the implication

f′_{ω}(L) = f′_{ω}(2Λ − L) ⇒ f′′_{ω}(L) + f′′_{ω}(2Λ − L) < 0  (3.5)

which is equivalent to each of the implications

f′_{ω}(L) = f′_{ω}(2Λ − L) ⇒ 0 < f′′_{ω}(L) < |f′′_{ω}(2Λ − L)|,  (3.6)
f′_{ω}(L) − f′_{ω}(λ_{n}^{ω}) = f′_{ω}(2Λ − L) − f′_{ω}(λ_{n}^{ω}) ⇒ 0 < f_{ω}^{′′2}(L) < f_{ω}^{′′2}(2Λ − L).  (3.7)

We have used that L < λ_{n}^{ω} < 2Λ − L and f′′_{ω}(L) > 0, f′′_{ω}(2Λ − L) < 0 because of Lemma 2. If the inequality

μ (f′_{ω}(L) − f′_{ω}(λ_{n}^{ω})) + f_{ω}^{′′2}(L) < μ (f′_{ω}(2Λ − L) − f′_{ω}(λ_{n}^{ω})) + f_{ω}^{′′2}(2Λ − L)  (3.8)

is satisfied for a suitable Lagrangian multiplier μ then we get (3.7). For this, we prove the sharpened inequality

μ (f′_{ω}(L) − f′_{ω}(λ_{n}^{ω})) + f_{ω}^{′′2}(L) < 0 < μ (f′_{ω}(2Λ − L) − f′_{ω}(λ_{n}^{ω})) + f_{ω}^{′′2}(2Λ − L)  (3.9)

studying the function

Q(L) := μ (f′_{ω}(L) − f′_{ω}(λ_{n}^{ω})) + f_{ω}^{′′2}(L)

for L ∈ I_{n}^{0} and the special multiplier μ := −2f′′′_{ω}(λ_{n}^{ω}). Obviously, we have Q(λ_{n}^{ω}) = 0 and Q′(L) = (μ + 2f′′′_{ω}(L))f′′_{ω}(L). Applying the mean-value theorem on f′′_{ω} and f′′′_{ω} with respect to λ_{n}^{ω} and using Lemma 2 we get for the chosen parameter μ

Q′(L) = 2(L − λ_{n}^{ω})^{2}f_{ω}^{(4)}(L̃)f′′_{ω}(L̂) < 0

where L̃, L̂ ∈ (L, λ_{n}^{ω}) are intermediate values. Hence, the inequality (3.9) follows from Q(L) < Q(λ_{n}^{ω}) = 0 < Q(2Λ − L). Now, let be n = 2 and l_{1}^{ω} < L < 2Λ − L < l_{2}^{ω}. Because f′_{ω} is linear on (l_{1}^{ω}, l_{2}^{ω}) the first order necessary optimality condition (3.3) is satisfied for L = Λ only.

We denote the symmetric partition (Λ, Λ) as twin solution of problem (^{2}P^{ω,Λ}).

Corollary 2. For L_{1}, L_{2} ∈ (l_{n−1}^{ω}, l_{n}^{ω}) the twin solution is the only local minimal solution of Problem (^{2}P^{ω,Λ}) on I_{n}^{0} × I_{n}^{0} if

a) n = 2 or

b) n ≥ 3 and Λ ∈ (l_{n−1}^{ω}, λ_{n}^{ω}).

Proof. Because of Theorem 2, only the symmetric pair (Λ, Λ) may be a local minimal solution of problem (^{2}P^{ω,Λ}) on I_{n}^{0} × I_{n}^{0}. Condition (3.3) holds for L_{1} = L_{2} = Λ. The sufficient optimality condition 2f′′_{ω}(Λ) > 0 is satisfied for n = 2 and for n ≥ 3 if Λ < λ_{n}^{ω} because of Lemma 2.

The twin solution corresponds to a pair of almost regular ω-inpolyeders. In case n ≥ 3, it is locally minimal if the defect angle is sufficiently small in the sense of (n − 1) sin \frac{δ(Λ)}{2} < sin \frac{α(Λ)}{2}. This corresponds to f′′_{ω}(Λ) > 0 for Λ < λ_{n}^{ω}.

Corollary 3. Let n ≥ 3 and λ_{n}^{ω} < Λ < l_{n}^{ω}. Then the twin solution is a local maximum of (^{2}P^{ω,Λ}) with

2f_{ω}(Λ) > \{ \begin{matrix}f_{ω}(l_{n−1}^{ω}) + f_{ω}(2Λ − l_{n−1}^{ω}) & if Λ ∈ I_{n}^{−} \\ f_{ω}(l_{n}^{ω}) + f_{ω}(2Λ − l_{n}^{ω}) & if Λ ∈ I_{n}^{+}. \end{matrix}

Proof. Let L_{1} = L. The objective function ^{2}f_{ω}(L, 2Λ−L) of problem (Q_{0}^{ω,Λ}) is continuous on the interval

I_{n}^{0} ∩ (2Λ − l_{n}^{ω}, Λ] = \{ \begin{matrix}(l_{n−1}^{ω}, Λ] & for Λ ∈ I_{n}^{−} \\ (2Λ − l_{n}^{ω}, Λ] & for Λ ∈ I_{n}^{+}. \end{matrix}

For Λ ∈ (λ_{n}^{ω}, l_{n}^{ω}) we have f′′_{ω}(Λ) < 0 from Lemma 2. This means that L = Λ is a local maximum of ^{2}f_{ω}(L, 2Λ − L). Theorem 2 says that there are no local minimal points on I_{n}^{0}∩(2Λ−l_{n}^{ω}, Λ). Therefore, the function ^{2}f_{ω}(L, 2Λ−L) is strictly monotonously increasing on I_{n}^{0} ∩ (2Λ − l_{n}^{ω}, Λ] which completes the proof.

In the case Λ ∈ (λ_{n}^{ω}, l_{n}^{ω}) we have found the better but nonsymmetric partitions (l_{n−1}^{ω}, 2Λ − l_{n−1}^{ω}) and (2Λ − l_{n}^{ω}, l_{n}^{ω}), resp.

3.2. Nonsymmetric and Regular Symmetric Solutions

We consider case 2 and investigate the nonsymmetric partitions of Corollary 3 with respect to global minimality of ^{2}f_{ω} on [\underline{L}_{ω}, Λ] × [Λ, ω]\(I_{n}^{0} × I_{n}^{0}). For this, we interprete a pair of ω-inpolyeders as one 2ω-inpolyeder and embed the partition problem (^{2}P^{ω.Λ}) in the basic problem (P^{2ω,2Λ}). Case 2.1: Λ ∈ I_{n}^{+}, L_{2} ≥ l_{n}^{ω}, n ≥ 2. We modify (P^{2ω,2Λ}) by adding condition (+) and get the problem

(P_{+}^{2ω,2Λ})  F_{2ω}(φ, m) = \frac{1}{2} ∑_{i=n}^{m} sin φ_{i} → Min!

L_{2ω}(φ, m) = 2 ∑_{i=1}^{m} sin \frac{φ_{i}}{2} = 2Λ

∑_{i=1}^{m} φ_{i} = 2ω
0 < φ_{i} < π for i = 1, ..., m
(+)  φ_{i} ≤ α_{n}^{ω}  for i = 1, ..., n + 1.

This problem results from problem (P^{2ω,2Λ}) by adding the condition (+) which ensures that an almost regular twin solution does not correspond to a feasible solution of (P_{+}^{2ω,2Λ}). Moreover, feasible solutions of (^{2}P^{ω.Λ}) with L_{2} < l_{n}^{ω} are excluded.

Lemma 5. A feasible solution of (^{2}P^{ω.Λ}) corresponds to a feasible solution of (P_{+}^{2ω,2Λ}) iff L_{2} ≥ l_{n}^{ω}.

Proof. a) Let L_{2} < l_{n}^{ω}. Then L_{1} > l_{n−1}^{ω} follows from (3.2). Each pair (P_{ω,1}, P_{ω,2}) with L(P_{ω,i}) = L_{i} (i = 1, 2) is associated with 2(n − 1) central angles α_{ω}(L_{i}) ∈ (α_{n}^{ω}, α_{n−1}^{ω}) and two defect angles 0 < δ_{ω}(L_{i}) < α_{ω}(L_{i}) (see Theorem 1). Therefore, condition (+) cannot be fulfilled.

b) Let L_{2} = l_{n}^{ω}. From Λ ∈ I_{n}^{+} and L_{1} = 2Λ − L_{2} ≤ L_{2} follows L_{1} > l_{n−1}^{ω}. We get the representations

P_{ω,1} = [ \underbrace{α, ..., α}_{n−1}, δ], P_{ω,2} = [ \underbrace{α_{n}^{ω}, ..., α_{n}^{ω}}_{n} ]

with α_{n}^{ω} ≤ α < α_{n−1}^{ω} and δ = ω − (n − 1)α ≤ α_{n}^{ω}. Condition (+) is fulfilled.

c) Let L_{2} > l_{n}^{ω}. Then, condition (+) follows from

P_{ω,2} = [ \underbrace{α, ..., α}_{n}, δ]

with α < α_{n}^{ω} and δ ≤ α.

Now, we discuss necessary conditions for an optimal solution (φ, m) of problem (P_{+}^{2ω,2Λ}). Each such (φ, m) represents a 2ω-inpolyeder P_{2ω} with q central angles φ_{1} = ... = φ_{q} = α_{n}^{ω} for some q ≥ 0, n + 1 − q central angles φ_{i} < α_{n}^{ω} for i = q + 1, ..., n + 1 and remaining φ_{i} ∈ (0, π). We decompose P_{2ω} into the inpolyeders P_{q·α_{n}^{ω}} and P_{ξ} with ξ := 2ω−q·α_{n}^{ω}. The q · α_{n}^{ω}-inpolyeder is a regular one with L(P_{q·α_{n}^{ω}}) = l_{q}^{q·α_{n}^{ω}} = 2q sin \frac{ω}{2n} (if q ≥ 1). The central angles of the ξ-inpolyeder P_{ξ} are free variables with respect to the inequality restrictions (+) of (P_{+}^{2ω,2Λ}). Hence, P_{ξ} corresponds to an optimal solution of problem (P^{ξ,L_{ξ}}) with L_{ξ} := 2Λ − l_{q}^{q·α_{n}^{ω}}. This means that P_{ξ} is a well-determined almost regular (p + 1)-sided ξ-inpolyeder with p from L_{ξ} ∈ (l_{p}^{ξ}, l_{p+1}^{ξ}]. For P_{2ω} we get the representation

P_{2ω} = [ \underbrace{α_{n}^{ω}, ..., α_{n}^{ω}}_{q}, δ, \underbrace{α, ..., α}_{p} ]  (3.10)

2ω = q · α_{n}^{ω} + δ + p · α,  (3.11)
L(P_{2ω}) = l_{q}^{q·α_{n}^{ω}} + l_{ξ}(α)  (3.12)

where α, δ are uniquely determined by L_{ξ} = l_{ξ}(α) and δ = ξ − p · α, 0 < δ ≤ α (see (2.7) and Theorem 1). Therefore, the structure of an optimal solution (φ, m) of (P_{+}^{2ω,2Λ}) is given by

φ = ( \underbrace{α_{n}^{ω}, ..., α_{n}^{ω}}_{q}, δ, \underbrace{α, ..., α}_{p} ), m = q + 1 + p.  (3.13)

Condition (+) leads to the alternative

either α ≤ α_{n}^{ω}
or α > α_{n}^{ω} and q ≥ n. (3.14)

For such central angles we discuss the isoperimetric condition.

Lemma 6. Let (φ, m) satisfy (3.13). Then the following implication holds:

α \{ \begin{matrix}< \\ = \\ > \end{matrix} \} α_{n}^{ω} ⟹ L_{2ω}(φ, m) \{ \begin{matrix}> \\ = \\ < \end{matrix} \} 2l_{n}^{ω}.

Proof. For α = α_{n}^{ω} = \frac{ω}{n} we get δ = α_{n}^{ω} from (3.11) and 0 < δ ≤ α. This implies m = 2n, 2ω = 2n · α_{n}^{ω} and L_{2ω}(φ, m) = 4n sin \frac{ω}{2n} = 2l_{n}^{ω} = l_{2ω}(α_{n}^{ω}). For each q ≥ 0 we consider the decomposition l_{2ω}(α_{n}^{ω}) = l_{q·α_{n}^{ω}}(α_{n}^{ω}) + l_{ξ}(α_{n}^{ω}) with ξ = 2ω − q · α_{n}^{ω}. Because the function l_{ξ} is strictly monotonously decreasing for increasing α the required implication is proved.

Lemma 5 and Lemma 6 allow to derive the minimal partition (L_{1}, L_{2}) in case 2.1.

Theorem 3. Let Λ ∈ I_{n}^{+} and L_{2} ≥ l_{n}^{ω}. Then the optimal solution of problem (P_{+}^{2ω,2Λ}) is uniquely determined by m = 2n and φ according (3.13) with q = n, p = n − 1, α = α_{ω}(2Λ − l_{n}^{ω}) ∈ [α_{n}^{ω}, α_{n−1}^{ω}). This solution corresponds to the minimal solution (L_{1}, L_{2}) of 2f_{ω} on [\underline{L}_{ω}, 2Λ − l_{n}^{ω}) × [l_{n}^{ω}, ω] with L_{2} = l_{n}^{ω} and L_{1} ∈ (l_{n−1}^{ω}, l_{n}^{ω}].

Proof. From L_{2ω}(φ, m) = 2Λ ≤ 2l_{n}^{ω} we can exclude α < α_{n}^{ω} because of Lemma 6. For L_{2ω}(φ, m) = 2l_{n}^{ω} follows α = α_{n}^{ω}, δ = α_{n}^{ω} and m = 2n from Lemma 6. These angles correspond to the feasible pair (L_{1}, L_{2}) = (l_{n}^{ω}, l_{n}^{ω}) of problem (^{2}P^{ω,Λ}). For L_{2ω}(φ, m) = 2Λ < 2l_{n}^{ω} we get α > α_{n}^{ω} from Lemma 6 and q ≥ n from (3.14). Assuming q > n. Then, the corresponding (φ̃, m) from (3.13) cannot be optimal. To show this we consider the decomposition φ̃ = (Ψ^{1}, Ψ̃^{2}) with

Ψ^{1} = ( \underbrace{α_{n}^{ω}, ..., α_{n}^{ω}}_{n} ), Ψ̃_{2} = ( \underbrace{α_{n}^{ω}, ..., α_{n}^{ω}}_{q−n}, δ, \underbrace{α, ..., α}_{p} )

and ω = n · α_{n}^{ω} = (q − n) · α_{n}^{ω} + δ + p · α. A corresponding decomposition is possible for the objective function

F_{2ω}(φ̃, m) = F_{ω}(Ψ^{1}, n) + F_{ω}(Ψ̃^{2}, m − n)

and the restriction function

L_{2ω}(φ̃, m) = L_{ω}(Ψ^{1}, n) + L_{ω}(Ψ̃^{2}, m − n).

Obviously, L_{ω}(Ψ^{1}, n) = l_{n}^{ω} and F_{ω}(Ψ^{1}, n) = f_{ω}(l_{n}^{ω}). We use the notation L̃ := L_{ω}(Ψ̃^{2}, m − n). Taking into account L_{2ω}(φ̃, m) = 2Λ we get L̃ = 2Λ−l_{n}^{ω} ∈ (l_{n−1}^{ω}, l_{n}^{ω}] because of Λ ∈ I_{n}^{+}. The pair (Ψ̃^{2}, m − n) is a feasible solution of the basic problem (P^{ω,L̃}). It is not optimal because Theorem 1 yields the unique optimal solution

Ψ^{2} = ( \underbrace{α, ..., α}_{n−1}, δ), α ∈ [α_{n}^{ω}, α_{n−1}^{ω}).

The corresponding composition (φ, m) = ((Ψ^{1}, Ψ^{2}), 2n) is feasible in problem (P_{+}^{2ω,2Λ}) because of δ = ω − (n − 1)α < α_{n}^{ω}. This pair (φ, m) is one of structure (3.13) with q = n, m = 2n and

F_{2ω}(φ̃, m) > f_{ω}(l_{n}^{ω}) + f_{ω}(L̃) = F_{2ω}(φ, 2n).

This means that (φ, 2n) represents the optimal solution of (P_{+}^{2ω,2Λ}). The corresponding 2ω-inpolyeder P_{2ω} is composed by two almost regular ω-inpolyeders. Hence the pair (L̃, l_{n}^{ω}) is feasible and therefore optimal in (^{2}P^{ω,Λ}) because of Lemma 5.

Case 2.2: Λ ∈ I_{n}^{−}, L_{1} ≤ l_{n−1}^{ω}, n ≥ 2. This case is treated in an analogous way as case 2.1. Problem (P^{2ω,2Λ}) is modified by adding condition (–) which excludes feasible solutions of (^{2}P^{ω,Λ}) with L_{1} > l_{n−1}^{ω}.

We consider the problem

(P_{−}^{2ω,2Λ})  F_{2ω}(φ, m) = \frac{1}{2} ∑_{i=n}^{m} sin φ_{i} → Min!

L_{2ω}(φ, m) = 2 ∑_{i=1}^{m} sin \frac{φ_{i}}{2} = 2Λ

∑_{i=1}^{m} φ_{i} = 2ω
0 < φ_{i} < π for i = 1, ..., m
(−)  φ_{i} ≤ α_{0,n}  for i = 1, ..., n.

In this, α_{0,n} is implicitely defined by

l_{ω}(α_{0,n}) = 2Λ − l_{n−1}^{ω} =: l_{0,n}.  (3.15)

Condition Λ ∈ I_{n}^{−} implies

l_{n−1}^{ω} < Λ < l_{0,n} ≤ l_{n}^{ω}  (3.16)

and therefore

α_{n}^{ω} ≤ α_{0,n} < α_{ω}(Λ) < α_{n−1}^{ω}  (3.17)

and

0 < δ_{0,n} := ω − (n − 1)α_{0,n} ≤ α_{0,n}.  (3.18)

The effect of the additional restriction (–) describes the following lemma.

Lemma 7. A feasible solution of (^{2}P^{ω,Λ}) corresponds to a feasible solution of (P_{−}^{2ω,2Λ}) iff L_{1} ≤ l_{n−1}^{ω}.

Proof. a) If L_{1} > l_{n−1}^{ω} then L_{1} ≤ L_{2} = 2Λ − L_{1} < l_{0,n} ≤ l_{n}^{ω}. Each pair (P_{ω,1}, P_{ω,2}) with L(P_{ω,i}) = L_{i} corresponds to 2(n − 1) central angles α_{ω}(L_{i}) > α_{0,n} and two defect angles δ_{ω}(L_{i}) < δ_{0,n}. Restriction (–) is violated.

b) If L_{1} ≤ l_{n−1}^{ω} then L_{2} ≥ l_{0,n} > l_{n−1}^{ω}. In this case, a feasible solution of (^{2}P^{ω,Λ}) contains at least n−1 central angles α with α_{n}^{ω} ≤ α ≤ α_{0,n} and one defect angle δ with δ ≤ α_{n}^{ω} ≤ α_{0,n}. Restriction (–) is fulfilled.

The additional condition (–) enables us to investigate case 2.2. by means of problem (P_{−}^{2ω,2Λ}). A feasible solution of this problem contains q ≥ 0 angles φ_{i} = α_{0,n} and m − q free angles with respect to restriction (–). For an optimal solution the last ones describe an almost regular inpolyeder P_{ξ} with L_{ξ} := 2Λ − l_{q}^{q·α_{0,n}}. The corresponding 2ω-inpolyeder has the representation

P_{2ω} = [ \underbrace{α_{0,n}, ..., α_{0,n}}_{q}, δ, \underbrace{α, ..., α}_{p} ]  (3.19)

2ω = q · α_{0,n} + δ + p · α  (3.20)
L(P_{2ω}) = l_{q}^{q·α_{0,n}} + l_{ξ}(α)  (3.21)

where p, α, δ are uniquely determined by L_{ξ} ∈ (l_{p}^{ξ}, l_{p+1}^{ξ}], L_{ξ} = l_{ξ}(α) and δ = ξ − p · α, 0 < δ ≤ α. An optimal solution of (P_{−}^{2ω,2Λ}) is of the structure

φ = ( \underbrace{α_{0,n}, ..., α_{0,n}}_{q}, δ, \underbrace{α, ..., α}_{p} ), m = q + 1 + p  (3.22)

with L(φ, m) from (3.21). Restriction (–) implies the alternative

either α ≤ α_{0,n}
or α > α_{0,n} and q ≥ n − 1.

(3.23)

Lemma 8. For (φ, m) from (3.22) the following implication holds:

α \{ \begin{matrix}< \\ = \\ > \end{matrix} \} α_{0,n} ⟹ L_{2ω}(φ, m) \{ \begin{matrix}> \\ = \\ < \end{matrix} \} l_{2ω}(α_{0,n})

Proof. For α = α_{0,n} we get L_{2ω}(φ, m) = l_{2ω}(α_{0,n}). Lemma 3 yields l_{2ω}(α_{0,n}) = l_{qα_{0,n}}(α_{0,n}) +l_{ξ}(α_{0,n}) with ξ = δ + p · α_{0,n} . Taking into account that l_{ξ} is strictly monotonously decreasing in α the proof is complete. From Lemma 7 and Lemma 8 we get an analogous result to Theorem 3.

Theorem 4. Let Λ ∈ I_{n}^{−} and L_{1} ≤ l_{n−1}^{ω}. Then the optimal solution of problem (P_{−}^{2ω,2Λ}) is uniquely determined by m = 2n and φ according (3.22) with q = n − 1, p = n − 1, α = α_{0,n} ∈ [α_{n}^{ω}, α_{n−1}^{ω}). This solution corresponds to the minimal solution (L_{1}, L_{2}) of ^{2}f_{ω} on [\underline{L}_{ω}, l_{n−1}^{ω}] × [2Λ − l_{n−1}^{ω}, ω] with L_{1} = l_{n−1}^{ω} and L_{2} ∈ (l_{n−1}^{ω}, l_{n}^{ω}].

Proof. From ω = (n − 1)α_{n−1}^{ω} = (n − 1)α_{0,n} + δ_{0,n} (see (3.18)) follows

2ω = (n − 1)α_{n−1}^{ω} + δ_{0,n} + (n − 1)α_{0,n}.  (3.24)

Lemma 4, (3.15), (3.17) and the monotonity of l_{ω+δ_{0,n}}(α) imply the estimate

2Λ = l_{ω}(α_{0,n}) + l_{ω}(α_{n−1}^{ω})
= l_{(n−1)α_{0,n}}(α_{0,n}) + l_{ω+δ_{0,n}}(α_{n−1}^{ω})  (3.25)
< l_{(n−1)α_{0,n}}(α_{0,n}) + l_{ω+δ_{0,n}}(α_{0,n}) = l_{2ω}(α_{0,n}).

By means of Lemma 8 we can exclude the case α ≤ α_{0,n}.

For α > α_{0,n} we have q ≥ n−1 from (3.23). The corresponding φ̃ is decomposed according φ̃ = (Ψ^{1}, Ψ̃^{2}) with

Ψ^{1} = (\underbrace{α_{0,n}, ..., α_{0,n}}_{n−1}), Ψ̃^{2} = (\underbrace{α_{0,n}, ..., α_{0,n}}_{q−n+1}, δ, \underbrace{α, ..., α}_{p}).

This leads to the decompositions

F_{2ω}(φ̃, m) = F_{(n−1)α_{0,n}}(Ψ^{1}, n − 1) + F_{ρ}(Ψ̃^{2}, m − n + 1)

and

L_{2ω}(φ̃, m) = L_{(n−1)α_{0,n}}(Ψ^{1}, n − 1) + L_{ρ}(Ψ̃_{2}, m − n + 1)

with ρ = 2ω − (n − 1)α_{0,n} = ω + δ_{0,n} (see (3.24)). From L_{(n−1)α_{0,n}}(Ψ^{1}, n − 1) = l_{(n−1)α_{0,n}}(α_{0,n}) = l_{n−1}^{(n−1)α_{0,n}} we get F_{(n−1)α_{0,n}}(Ψ^{1}, n − 1) = f_{(n−1)α_{0,n}}(l_{n−1}^{(n−1)α_{0,n}}). For L̃ := 2Λ − l_{(n−1)α_{0,n}}(α_{0,n}) = l_{ρ}(α_{n−1}^{ω}) we consider the problem (P^{ρ,L̃}) with the feasible solution (Ψ̃_{2}, m − n + 1) . It follows

α_{n}^{ρ} = \frac{ρ}{n} = \frac{2ω − (n − 1)α_{0,n}}{n} = \frac{(n − 1)α_{n−1}^{ω} + δ_{0,n}}{n} < α_{n−1}^{ω}

and

α_{n−1}^{ρ} = \frac{ρ}{n − 1} = α_{n−1}^{ω} + \frac{δ_{0,n}}{n − 1} > α_{n−1}^{ω}

from (3.17), (3.18) and (3.24). This implies L̃ ∈ (l_{n−1}^{ρ}, l_{n}^{ρ}). Hence, from Theorem 1 it follows that the pair (Ψ^{2}, n) with Ψ^{2} = (\underbrace{α_{n−1}^{ω}, ..., α_{n−1}^{ω}}_{n−1}, δ_{0,n}) is optimal in (P^{ρ,L̃}). The

composed pair (φ, 2n − 1) with φ = (Ψ^{1}, Ψ^{2}) satisfies

F_{2ω}(φ̃, m) ≥ f_{(n−1)α_{0,n}}(2Λ − L̃) + f_{ρ}(L̃) = F_{2ω}(φ, 2n − 1)

for φ̃ from (3.22). This means that (φ, 2n − 1) of structure (3.22) with α = α_{n−1}^{ω} and q = n − 1 represents the optimal solution of (P_{−}^{2ω,2Λ}). It corresponds to a pair of almost regular ω-inpolyeders with p-perimeters l_{n−1}^{ω}, 2Λ − l_{n−1}^{ω}. This pair yields a feasible and therefore optimal solution of (^{2}P^{ω,Λ}) on [\underline{L}_{ω}, l_{n−1}^{ω}] × [2Λ − l_{n−1}^{ω}, ω] because of Lemma 7.

In case 2, nonsymmetric partitions turned out to be minimal. Moreover, a regular (n − 1)- or n-sided ω-inpolyeder belongs to this partition.

4. Solution Branching and Global Solution

In the previous section we have shown that the symmetric as well as a nonsymmetric partition come into consideration as solution of our isoperimetric partition problem. Let Λ ∈ (l_{n−1}^{ω}, l_{n}^{ω}], then the following partitions may be optimal:

(TS) a pair (P_{ω}, P_{ω}) of two equal n-sided almost regular ω-inpolyeders, (NS_{+}) a pair (P_{ω}, P_{n}^{ω}) of a regular n-sided ω-inpolyeder P_{n}^{ω} and an almost regular n-sided

ω-inpolyeder P_{ω} for Λ ∈ I_{n}^{+}, (NS_{−}) a pair (P_{n−1}^{ω}, P_{ω}) of a regular (n−1)-sided ω-inpolyeder P_{n−1}^{ω} and an almost regular

n-sided ω-inpolyeder P_{ω} for Λ ∈ I_{n}^{−}.

In these partitions the number of chords between P_{ω,1} and P_{ω,2} differs at most by one. Always a regular ω-inpolyeder belongs to the nonsymmetric partition. We have found these solutions as minimal points of the objective function^{2}f_{ω} over disjunct parts of the feasible domain, namely Case 1: L_{1} = L_{2} = Λ

with ^{2}f_{ω}(L_{1}, L_{2}) = 2f_{ω}(Λ) for n = 2 or Λ < λ_{n}^{ω},

Case 2.1: L_{2} = l_{n}^{ω}, L_{1} = 2Λ − l_{n}^{ω} ∈ (l_{n−1}^{ω}, l_{n}^{ω}]

with ^{2}f_{ω}(L_{1}, L_{2}) = f_{ω}(2Λ − l_{n}^{ω}) + f_{ω}(l_{n}^{ω}),

Case 2.2: L_{1} = l_{n−1}^{ω}, L_{2} = 2Λ − l_{n−1}^{ω} ∈ (l_{n−1}^{ω}, l_{n}^{ω}] with ^{2}f_{ω}(L_{1}, L_{2}) = f_{ω}(l_{n−1}^{ω}) +f_{ω}(2Λ − l_{n−1}^{ω}).

For taking a decision about the global minimal solution of problem (^{2}P^{ω,Λ}) we consider the following defect function:

D_{ω}^{n}(Λ) := \{ \begin{matrix}f_{ω}(l_{n−1}^{ω}) + f_{ω}(2Λ − l_{n−1}^{ω}) − 2f_{ω}(Λ) & for Λ ∈ I_{n}^{−} \\ f_{ω}(2Λ − l_{n}^{ω}) + f_{ω}(l_{n}^{ω}) − 2f_{ω}(Λ) & for Λ ∈ I_{n}^{+} . \end{matrix}  (4.1)

The sign of this continuous function determines the solution of our problem.

4.1. Convexity defect

The function \frac{1}{2}D_{ω}^{n} describes a convexity defect of the fonction penetrante f_{ω} over I_{n} in the following sense.

Definition 4. Let f : [0, 1] → R be a continuous function. Then the functions

\begin{aligned}φ_{f,0}(x) & := \frac{1}{2}(f(0) + f(2x)) − f(x)  for x ∈ [0, \frac{1}{2}] \\ φ_{f,1}(x) & := \frac{1}{2}(f(1) + f(2x − 1)) − f(x)  for x ∈ [\frac{1}{2}, 1] \end{aligned}

are called the left-sided and the right-sided convexity defect of f, respectively. The function

φ_{f}(x) := \{ \begin{matrix}φ_{f,0}(x) & for x ∈ [0, \frac{1}{2}] \\ φ_{f,1}(x) & for x ∈ [\frac{1}{2}, 1] \end{matrix}

is called convexity defect of f.

We study zeros of φ_{f} under well-defined conditions on f.

Lemma 9. Let f : [0, 1] → R be a twice differentiable function on (0,1) and ξ ∈ (0, 1) a unique turning point of f with f′′(x) > 0 for x < ξ and else f′′(x) < 0. Then, the convexity defect φ_{f} of f has a unique zero x_{0} ∈ (0, 1) with

a) x_{0} ∈ (0, \frac{1}{2}] for φ_{f}(\frac{1}{2}) ≤ 0,

b) x_{0} ∈ [\frac{1}{2}, 1] for φ_{f}(\frac{1}{2}) ≥ 0.

Proof. a) Let x ∈ (0, \frac{1}{2}]. From f′′(x) > 0 on (0, ξ) it follows f′(2x) > f′(x) on (0, \frac{1}{2}ξ) and therefore φ′_{f}(x) > 0 on (0, \frac{1}{2}ξ). Together with φ(0) = 0 we get φ_{f}(x) > 0 on (0, \frac{1}{2}ξ). The function φ_{f} is strictly concave on (\frac{1}{2}ξ, ξ) ∩ (\frac{1}{2}ξ, \frac{1}{2}) because φ′′_{f}(x) < 0 for the corresponding x. If ξ < \frac{1}{2} then we use φ′_{f}(x) < 0 on (ξ, \frac{1}{2}). Thus, there exists a unique zero x_{0} ∈ (\frac{1}{2}ξ, \frac{1}{2}] of φ_{f} in case φ_{f}(\frac{1}{2}) ≤ 0.

b) Let x ∈ [\frac{1}{2}, 1]. We consider the reflected function g(y) = −f(1 − y) for y ∈ [0, 1] and use the connection φ(y) = −φ_{f}(x) for y ∈ [0, \frac{1}{2}], x = 1 − y. The existence of a unique zero y_{0} ∈ (0, \frac{1}{2}] in case φ_{g}(\frac{1}{2}) ≤ 0 follows from part a). This proves part b).

4.2. Global Minimum

The analytical properties of f_{ω} described in Lemma 1 and Lemma 2 are transfered to the function f(x) = f_{ω}(Λ(x)) with Λ(x) = l_{n−1}^{ω} + x(l_{n}^{ω} − l_{n−1}^{ω}), n ≥ 3 and x ∈ [0, 1]. The convexity defect is given by φ_{f}(x) = \frac{1}{2}D_{ω}^{n}(Λ(x)). Lemma 9 ensures the existence of a unique zero ^{2}λ_{n}^{ω} ∈ I_{n}^{0} of D_{ω}^{n}(Λ) on I_{n}^{0} where

D_{ω}^{n}(Λ) \{ \begin{matrix}> 0 & for Λ ∈ (l_{n−1}^{ω},^{2} λ_{n}^{ω}) \\ < 0 & for Λ ∈ (^{2}λ_{n}^{ω}, l_{n}^{ω}) \end{matrix}  (4.2)

and

either ^{2}λ_{n}^{ω} ∈ I_{n}^{−} for D_{ω}^{n}(\frac{1}{2}(l_{n−1}^{ω} + l_{n}^{ω})) ≤ 0

or ^{2}λ_{n}^{ω} ∈ I_{n}^{+} for D_{ω}^{n}(\frac{1}{2}(l_{n−1}^{ω} + l_{n}^{ω})) > 0.

(4.3)

The defect function D_{ω}^{n} from (4.1) compares parametrically in Λ objective values of ^{2}f_{ω} coming into consideration as global minimal solutions of (^{2}P^{ω,Λ}). Relations (4.2) and (4.3) show that ^{2}λ_{n}^{ω} describes a branch point for the solution structure if n ≥ 3. It is related to the turning point λ_{n}^{ω} as follows.

Lemma 10. The branch point ^{2}λ_{n}^{ω} (n ≥ 3) satisfies

\frac{1}{2}(l_{n−1}^{ω} + λ_{n}^{ω}) ≤ ^{2}λ_{n}^{ω} ≤ λ_{n}^{ω}.

Proof. Corollary 3 implies D_{ω}^{n}(Λ) < 0 for every Λ ∈ (λ_{n}^{ω}, l_{n}^{ω}] and therefore ^{2}λ_{n}^{ω} ≤ λ_{n}^{ω} for the zero ^{2}λ_{n}^{ω} of D_{ω}^{n}.

To verify the lower bound we distinguish two cases.

a) D_{ω}^{n}(\frac{1}{2}(l_{n−1}^{ω} + l_{n}^{ω})) ≤ 0: We consider f(x) = f_{ω}(Λ(x)) with Λ(x) = l_{n−1}^{ω} + x(l_{n}^{ω} − l_{n−1}^{ω}), x ∈ [0, 1] and λ_{n}^{ω} = Λ(ξ), ^{2}λ_{n}^{ω} = Λ(x_{0}). Using x_{0} ≥ \frac{1}{2}ξ from the proof of Lemma 9 we get ^{2}λ_{n}^{ω} ≥ \frac{1}{2}(l_{n−1}^{ω} + λ_{n}^{ω}).

b) D_{ω}^{n}(\frac{1}{2}(l_{n−1}^{ω} + l_{n}^{ω})) ≥ 0: The lower bound results from x_{0} ≥ \frac{1}{2} and l_{n}^{ω} ≥ λ_{n}^{ω}.

For n = 2, the strict convexity of f_{ω} on I_{2} implies

D_{ω}^{2}(Λ) > 0 for Λ ∈ I_{2}^{0}.  (4.4)

This means that there is no branch point for Λ ∈ I_{2}. These results allow us to identify the global minimal solution of the partition problem (^{2}P^{ω,Λ}).

Theorem 5. Let n be determined according Λ ∈ (l_{n−1}^{ω}, l_{n}^{ω}]. If n = 2 then the optimal solution of the partition problem is given by the twin solution (TS). If n ≥ 3 then there exists a unique zero ^{2}λ_{n}^{ω} of the defect function D_{n}^{ω} on I_{n}^{0} describing a branching of the solution of the partition problem in the following manner:

(i) for Λ ∈ (l_{n−1}^{ω},^{2}λ_{n}^{ω}) the twin solution (TS) is optimal, (ii) for Λ = ^{2}λ_{n}^{ω} the double solution (TS) and either (NS_{+}) for ^{2}λ_{n}^{ω} ∈ I_{n}^{+} or (NS_{−}) for

2λ_{n}^{ω} ∈ I_{n}^{−} is optimal, (iii) for Λ ∈ (^{2}λ_{n}^{ω}, l_{n}^{ω}) the solution (NS_{+}) is optimal for Λ ∈ I_{n}^{+} and else (NS_{−}), (iv) for Λ = l_{n}^{ω} the coinciding solutions (TS) and (NS_{+}) are optimal.

Proof. From the Theorems 2, 3 and 4 it follows that only solutions (TS), (NS_{+}), (NS_{−}) may be optimal. These solutions are compared with each other via the defect function D_{n}^{ω}. If n = 2 then Corollary 2 and (4.4) yield the twin solution (TS) as optimal solution. For n ≥ 3 the existence of the unique zero^{2}λ_{n}^{ω} of D_{n}^{ω} on I_{n}^{0} (n ≥ 3) results from Lemma 9. This parameter value describes the change of the symmetric solution (TS) to a nonsymmetric solution (NS_{+}) or (NS_{−}), resp. Because of Corollary 2 and Lemma 10 solution (TS) is optimal for Λ ∈ (l_{n−1}^{ω},^{2}λ_{n}^{ω}). The other cases follow immediately.

We complete this section with a study about the asymptotic behaviour of the branch points 2λ_{n}^{ω}. Lemma 10 shows that the values ^{2}λ_{n}^{ω} are associated with the turning points λ_{n}^{ω}. We denote τ_{n}^{ω} = α_{ω}(λ_{n}^{ω}) and σ_{n}^{ω} = δ_{ω}(λ_{n}^{ω}) for L = λ_{n}^{ω} (see (2.11)) where (n − 1)τ_{n}^{ω} + σ_{n}^{ω} = ω, \frac{ω}{n} ≤ τ_{n}^{ω} ≤ \frac{ω}{n−1}, 0 ≤ σ_{n}^{ω} ≤ τ_{n}^{ω}. From f′′(λ_{n}^{ω}) = 0 it follows

(n − 1) sin \frac{σ_{n}^{ω}}{2} = sin \frac{τ_{n}^{ω}}{2} .  (4.5)

We use sin x = x+O(x^{3}) for sufficiently small x where \frac{O(h)}{h} is bounded for h → 0. Because of τ_{n}^{ω} = O(n^{−1}) and σ_{n}^{ω} ≤ τ_{n}^{ω} relation (4.5) implies

σ_{n}^{ω} = O(n^{−2})  (4.6)

for sufficiently large n.

Lemma 11. λ_{n}^{ω}, ^{2}λ_{n}^{ω} ∈ I_{n}^{−} for sufficiently large n.

Proof. We compare λ_{n}^{ω} − l_{n−1}^{ω} with l_{n}^{ω} − l_{n−1}^{ω} under consideration of (2.3) and λ_{n}^{ω} = 2(n − 1) sin \frac{τ_{n}^{ω}}{2} + 2 sin \frac{σ_{n}^{ω}}{2} . Using (4.5) and sin x = x − \frac{x^{3}}{3} + O(x^{5}) we get

\begin{aligned}\frac{λ_{n}^{ω} − l_{n−1}^{ω}}{l_{n}^{ω} − l_{n−1}^{ω}} & = \frac{−(n − 1)(τ_{n}^{ω})^{3} − (σ_{n}^{ω})^{3} + \frac{ω^{3}}{(n−1)^{2}} + O(n^{−4})}{ω^{3}(−\frac{1}{n^{2}} + \frac{1}{(n−1)^{2}} ) + O(n^{−4})} \\ & = \frac{ω^{3} − (n − 1)^{3}(τ_{n}^{ω})^{3} + O(n^{−2})}{ω^{3}(\frac{2}{n} − \frac{1}{n^{2}} ) + O(n^{−2})} \\ & = O(n^{−1}) \end{aligned}  (4.7)

and therefore ^{2}λ_{n}^{ω} ∈ I_{n}^{−} for sufficiently large n. Lemma 10 implies the same asymptotic behaviour for ^{2}λ_{n}^{ω}.

The optimal solution structure depending on the parameter Λ shows a jump at Λ = ^{2}λ_{n}^{ω}. For sufficiently large n the nonsymmetric solutions (NS_{−}) and (NS_{+}) both dominate. The numerical calculations show that ^{2}λ_{n}^{ω} ∈ I_{n}^{+} occurs for small n. In these cases the twin solution (TS) dominates.

5. Numerical Treatment

The branch point ^{2}λ_{n}^{ω} enables us to draw a decision about the solution pair of the partition problem. Because ^{2}λ_{n}^{ω} is the unique zero of the defect function we have to solve the nonlinear equation D_{n}^{ω}(Λ) = 0 on I_{n}^{0}.

However D_{ω}^{n} depends only implicitely on Λ. Therefore, we substitute this one equation by the following system of two nonlinear equations for corresponding central angles α_{Λ}, α_{L} ∈ [α_{n}^{ω}, α_{n−1}^{ω}]. The angle α_{Λ} corresponds to Λ, α_{n−1}^{ω} to l_{n−1}^{ω} and α_{L} to L = 2Λ − l_{n−1}^{ω}. We have to distinguish two cases according to (4.2), (4.3). For D_{n}^{ω}(\frac{1}{2}(l_{n−1}^{ω} + l_{n}^{ω}) ≤ 0 we get

f^{ω}(α_{n−1}^{ω}) + f^{ω}(α_{L}) − 2fω(α_{Λ}) = 0  (5.1)
l_{ω}(α_{n−1}^{ω}) + l_{ω}(α_{L}) − 2lω(α_{Λ}) = 0  (5.2)

with f^{ω}(α) = \frac{n−1}{2} sin α + \frac{1}{2} sin(ω − (n − 1)α) and l_{ω} from (2.2). In order to solve system (5.1), (5.2) the Newton method is used.

n D_{ω}^{n}(\frac{1}{2}(l_{n−1}^{ω} + l_{n}^{ω}))  ^{2}λ_{n}^{ω}
ω = 2π 3  2.825E-02  4.781149802531
4  -1.422E-03  5.421987271198
5  -1.968E-03  5.744385342918
6  -1.137E-03  5.917855737554
7  -6.256E-04  6.020537706570
8  -3.550E-04  6.085898726379
9  -2.104E-04  6.129868389893
10  -1.300E-04  6.160769675756
20  -4.720E-06  6.254828582382
ω = \frac{π}{3}  3  1.121 E-05  1.040450413358
4  1.766 E-07  1.043114785701
5  -2.245 E-07  1.044661940327
6  -1.443 E-07  1.045485013600
7  -8.096 E-08  1.045969679515
8  -4.614 E-08  1.046277086067
9  -2.735 E-08  1.046483299368
10  -1.689 E-08  1.046627899579
20  -6.090 E-10  1.047066101157

table 1

To specify a suitable initial point we follow the discussion in [1] where the algorithm is implemented in a Pascal program. For a suitable initial value Λ^{0} we determine α_{Λ}^{0} from l_{ω}(α_{Λ}^{0}) = Λ^{0} and α_{L}^{0} from l_{ω}(α_{L}^{0}) = 2Λ^{0} − l_{n−1}^{ω} by means of the Newton method. Consequently, the second equation (5.2) is fulfilled approximately for the initial point (α_{Λ}^{0}, α_{L}^{0}). Some results are given in table 1 for the central angles 2π and \frac{π}{3} , resp.

Concluding we illustrate the solution branching for ω = 2π and n = 4. The numerical computation yields D_{2π}^{4} (\frac{1}{2}(l_{3}^{2π} + l_{4}^{2π})) < 0. This implies ^{2}λ_{4}^{2π} ∈ (l_{3}^{2π}, \frac{1}{2}(l_{3}^{2π} + l_{4}^{2π})). If the parameter Λ is choosen according to the three cases

1. Λ ∈ (l_{3}^{2π},^{2}λ_{4}^{2π}) 2.1. Λ ∈ (^{2}λ_{4}^{2π}, \frac{1}{2}(l_{3}^{2π} + l_{4}^{2π})) 2.2. Λ ∈ (\frac{1}{2}(l_{3}^{2π} + l_{4}^{2π}), l_{4}^{2π}) we get three different solution structures (TS), (NS–), (NS+) of the partition problem as shown in figure 1.

figure 1

References

[1] Brach, A.: Zur Analysis von Favard’s ”fonction penetrante”. Diplomarbeit. Universität Leipzig 1994.

[2] Bonnesen, T.; Fenchel, W.: Theorie der konvexen Körper. Springer-Verlag Berlin 1934.

[3] Favard, J. M.: Problèmes d’Extremums Relatifs aux Courbes Convexes (I). Ann. Ec. Norm. 46 (1929).

[4] Fletcher, R.: Practical Methods of Optimization. John Wiley & Sons Chichester etc. 1987.

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

[6] Kripfganz, A.: The Generalized Favard Problem. Contributions to Algebra and Geometry 36 (1995), 185–202.

[7] Kripfganz, A.: Favard’s Fonction Penetrante – A Roughly Convex Function. To appear in: Optimization.