PUSHING DISKS APART - THE

KNESER-POULSEN CONJECTURE IN THE PLANE

Károly Bezdek and Robert Connelly

Eötvös University and Cornell University

July 31, 2001

Abstract. We give a proof of the planar case of a longstanding conjecture of Kneser (1955) and Poulsen (1954). In fact, we prove more by showing that if a finite set of disks in the plane is rearranged so that the distance between each pair of centers does not decrease, then the area of the union does not decrease, and the area of the intersection does not increase.

1. Introduction.

If p = (p_{1}, …, p_{N}) and q = (q_{1}, …, q_{N}) are two configurations of N points, where each p_{i} ∈ 𝔼^{n} and each q_{i} ∈ 𝔼^{n} is such that for all 1 ≤ i < j ≤ N, |p_{i} − p_{j}| ≤ |q_{i} − q_{j}|, we say that q is an expansion of p (and p is a contraction of q). If q is an expansion of p, then there may or may not be a continuous motion p(t) = (p_{1}(t), …, p_{N}(t)) for 0 ≤ t ≤ 1 such that p(0) = p and p(1) = q, and |p_{i}(t) − p_{j}(t)| is monotone increasing. When there is such a motion, we say that q is a continuous expansion of p. Let B(p_{i}, r_{i}) be the closed ball of radius r_{i} ≥ 0 in 𝔼^{n} about the point p_{i}, Vol_{n} represent the ndimensional volume, and | … | be the Euclidean norm, so |p_{i} − p_{j}| is the Euclidean distance between p_{i} and p_{j}.

In 1954 Poulsen [21] and in 1955 Kneser [18] independently conjectured the following for the case when r_{1} = ⋯ = r_{N}:

Conjecture 1. If q = (q_{1}, …, q_{N}) is an expansion of p = (p_{1}, …, p_{N}) in 𝔼^{n}, then

(1)  Vol_{n} [⋃_{i=1}^{N} B(p_{i}, r_{i})] ≤ Vol_{n} [⋃_{i=1}^{N} B(q_{i}, r_{i})] .

We will prove this conjecture for the case of the plane, n = 2, and with the same hypothesis the following related conjecture, which was mentioned in [17] by Klee and Wagon.

1991 Mathematics Subject Classification. 52A10, 52A40 (52A38, 51M25, 51M16).

The first author was partially supported by the Hung. Nat. Sci. Found. (OTKA), grant no.

T029786.

Conjecture 2. If q = (q_{1}, …, q_{N}) is an expansion of p = (p_{1}, …, p_{N}) in 𝔼^{n}, then

(2)  Vol_{n} [⋂_{i=1}^{N} B(p_{i}, r_{i})] ≥ Vol_{n} [⋂_{i=1}^{N} B(q_{i}, r_{i})] .

In [5] Bollobás proved Conjecture 1, for n = 2, when r_{1} = ⋯ = r_{N} and q is a continuous expansion of p. In [4] Bern and Sahai proved Conjecture 1 and Conjecture 2 for n = 2, but again with the additional assumption that q is a continuous expansion of p. Then in [11] Csikós extended Bollobás’s result to arbitrary radii for n = 2, and later in [10] Csikós proved Conjecture (1) under the assumption that q is a continuous expansion of p. In [7] Capoyleas showed (2) for congruent radii in the plane, but assuming that q is a continuous expansion of p. In [13] Gromov proved (2) for arbitrary radii, but only for N ≤ n + 1. Then in [8] Capoyleas and Pach proved (1) for arbitrary radii in all dimensions, but again only for N ≤ n + 1. In these cases, it is not hard to show that if q is an expansion of p, then it is a continuous expansion, a property that does not hold even for n + 2 points in 𝔼^{n}. In all of these cases, it is assumed or implicitly holds that the configuration q is a continuous expansion of p.

In the following, we will use a formula of Csikós describing the derivative of the volume of the union of 4-dimensional balls, when their centers are expanding smoothly, to show that the area of the union of 2-dimensional disks increases when one configuration of centers is an expansion of another, even when there is no continuous expansion in the plane. See Section 6 of this paper for a related result which is that a particular weighted surface volume changes monotonically under smooth continuous expansions. For such smooth continuous expansions this result extends the first result of Csikós in [11].

Conjecture 1, with all the radii equal, was repeated by Hadwiger in [14]. Later it was included in a list of problems by Valentine in [25], Klee in [16], Croft, Falconer, and Guy in [9], Moser and Pach in [20], and Klee and Wagon in [17], mentioning, in particular, the case of disks in the plane. This is the case that we prove here.

2. Connecting configurations in higher dimensions.

Our plan is to use results about continuous (or differentiable) motions of configurations of points in a higher dimension to get information about pairs of configurations in a lower dimension. The following lemma, which is fairly well-known, is essentially the same as formula (8) in Alexander [1], where the \sqrt{1 − t} and \sqrt{t} in Alexander’s formula is replaced by cos(πt) and sin(πt), respectively, and this is composed with a rotation to bring the final image back to the original copy of 𝔼^{n}. See Gromov [13], and Capolyeas and Pach [8], for a related result with a different proof. This allows us to connect configurations in a higher dimension. We regard 𝔼^{n} as the subset 𝔼^{n} = 𝔼^{n} × {0} ⊂ 𝔼^{n} × 𝔼^{n} = 𝔼^{2n}.

Lemma 1. Suppose that p = (p_{1}, …, p_{N}) and q = (q_{1}, …, q_{N}) are two configurations in 𝔼^{n}. Then the following is a continuous motion p(t) = (p_{1}(t), …, p_{N}(t)) in 𝔼^{2n}, that is analytic in t, such that p(0) = p, p(1) = q and for 0 ≤ t ≤ 1, |p_{i}(t) − p_{j}(t)| is monotone:

(3)  p_{i}(t) = (\frac{p_{i} + q_{i}}{2} + (cos πt)\frac{p_{i} − q_{i}}{2} , (sin πt)\frac{p_{i} − q_{i}}{2} ) , 0 ≤ i < j ≤ N.

Proof. We calculate:

4 |p_{i}(t) − p_{j}(t)|^{2} = |(p_{i} − p_{j}) − (q_{i} − q_{j})|^{2} + |(p_{i} − p_{j}) + (q_{i} − q_{j})|^{2}
+ 2(cos πt)(|p_{i} − p_{j}|^{2} − |q_{i} − q_{j}|^{2}).

This function is monotone, as required.

As stated here, the distances |p_{i}(t)−p_{j}(t)| could be monotone increasing or decreasing, but we will only need the case when q is an expansion of p and thus all distances are monotone increasing. (Of course, we regard the constant function as monotone.)

3. Main results.

We say that a configuration q = (q_{1}, …, q_{N}) is a piecewise-smooth expansion of p = (p_{1}, …, p_{N}) if q is a continuous expansion of p, and all the coordinates of all the points are infinitely differentiable functions of the parameter t except for a finite number of values of t. The following theorem and its corollaries are our main results. Also we regard 𝔼^{n} as the subset 𝔼^{n} = 𝔼^{n} × {0} ⊂ 𝔼^{n} × 𝔼^{2} = 𝔼^{n+2}.

Theorem 1. Let p = (p_{1}, …, p_{N}) and q = (q_{1}, …, q_{N}) be two configurations in 𝔼^{n} such that q is a piecewise-smooth expansion of p in 𝔼^{n+2}. Then the conclusions (1) and (2) of Conjecture 1 and Conjecture 2 hold in 𝔼^{n}.

The proof of this result will occupy the next few sections. The following includes the Kneser-Poulsen conjecture in the plane.

Corollary 1. Let p = (p_{1}, …, p_{N}) and q = (q_{1}, …, q_{N}) be two configurations in 𝔼^{2} such that q is an arbitrary expansion of p. Then (1) and (2) hold for n = 2.

Proof. Apply Lemma 1 to the configurations p and q to get that q is an analytic expansion of p in 𝔼^{4}. Then Theorem 1 applies, and the area inequalities follow.

The following is obtained by taking the limit as r → ∞ in Corollary 1, where r_{1} = ⋯ = r_{N} = r. It is one of the main results in [24] of Sudakov, in [1] of Alexander, and in [8] of Capoyleas and Pach. Although all these papers do not prove Corollary 1, it is explained carefully in [8] how to derive Corollary 2 from the Kneser-Poulsen conjecture in the plane.

Corollary 2. If q = (q_{1}, …, q_{N}) is an arbitrary expansion of p = (p_{1}, …, p_{N}) in 𝔼^{2}, then the length of the perimeter of the convex hull of p is less than or equal to the length of the perimeter of the convex hull of q.

The following is an immediate consequence of Theorem 1 and formula (3).

Corollary 3. If q = (q_{1}, …, q_{N}) is an arbitrary expansion of p = (p_{1}, …, p_{N}) in 𝔼^{n}, and the vectors p_{i} − q_{i}, for all 1 ≤ i ≤ N, lie in a 2-dimensional subspace of 𝔼^{n}, then both (1) and (2) hold.

The following related version of Theorem 1 follows from its proof. Right after the proof of Theorem 1 in Section 7 we will mention the adjustments for the proof of Remark 1.

Remark 1. Let p = (p_{1}, …, p_{N}) and q = (q_{1}, …, q_{N}) be two configurations in 𝔼^{n} such that for some integer m, q is a piecewise-smooth expansion of p in 𝔼^{m}, where the expansion is given by p(t), p(0) = p and p(1) = q, but the dimension of the affine span of p(t) = (p_{1}(t), …, p_{N}(t)) is at most (n + 2)-dimensional and is piecewise-constant. Then the conclusions (1) and (2) of Conjecture 1 and Conjecture 2 hold in 𝔼^{n}.

The following generalizes a result of Gromov in [13], who proved it in the case N ≤ n + 1.

Corollary 4. If q = (q_{1}, …, q_{N}) is an arbitrary expansion of p = (p_{1}, …, p_{N}) in 𝔼^{n}, and N ≤ n + 3, then then both (1) and (2) hold.

Proof. Apply Lemma 1, to get the analytic expansion p(t) for 0 ≤ t ≤ 1 between p and q. By taking the determinant of an appropriate number of coordinates of an appropriate subset of the vectors p_{i}(t) − p_{j}(t) it follows that the dimension of the affine span of p(t) is piecewise-constant. By assumption, the n + 3 points can have an affine span of dimension no larger than n + 2. Then Remark 1 applies.

As an example of how one might apply Theorem 1 in higher dimensions to expansions that are not continuous, we present the following result.

Corollary 5. Let q = (q_{1}, …, q_{N}) be an expansion of p = (p_{1}, …, p_{N}) in 𝔼^{n} such that for some λ > 1, for each i = 1, …, N either q_{i} = p_{i} or q_{i} = λp_{i}. Then q is a smooth expansion of p in 𝔼^{n+1} and thus (1) and (2) hold for any r_{i} > 0, for i = 1, …, N.

Proof. In the definition of the motion, we replace (3) with

p_{i}(t) = (\frac{p_{i} + q_{i}}{2} + (cos πt)\frac{p_{i} − q_{i}}{2} , (sin πt) |\frac{p_{i} − q_{i}}{2} |) , 1 ≤ i ≤ N,

which lives in 𝔼^{n+1}. To check that it is an expansion, consider any 1 ≤ i < j ≤ N. If either q_{i} = p_{i} or q_{j} = p_{j}, then a calculation similar to the one in the proof of Lemma 1 applies, and |p_{i}(t) − p_{j}(t)| is monotone increasing. Otherwise, consider the case when q_{i} = λp_{i} and q_{j} = λp_{j}. We calculate

\frac{d}{dt}|p_{i}(t)−p_{j}(t)|^{2} = \frac{π}{2} (λ−1)^{2}(sin πt)|p_{i}−p_{j}|^{2} [\frac{λ + 1}{λ − 1} + (cos πt) ((\frac{|p_{i}| − |p_{j}|}{|p_{i} − p_{j}|})^{2} − 1)] .

This is non-negative, which implies that |p_{i}(t) − p_{j}(t)| is monotone increasing.

See Section 8 for an example of this sort of expansion. For a different approach to the case when the configurations are similar see [6] by Bouligand. When the sets forming the union are not spherical balls, but translates of a convex set, then in [22], Rehder shows that the volume of the union does not decrease when the sets are dilated. However, a general expansive rearrangement of convex sets different from ellipsoids can have the volume of the intersection (union) increase (decrease), as shown in [19] by Meyer, Reisner and Schmuckenschläger.

3. Nearest point and farthest point Voronoi diagrams.

For a given configuration p = (p_{1}, …, p_{N}) of points in 𝔼^{n}, and radii r_{1}, …, r_{N}, consider the following sets:

C_{i} = { p_{0} ∈ 𝔼^{n} | for all j ≠ i, |p_{0} − p_{i}|^{2} − r_{i}^{2} ≤ |p_{0} − p_{j}|^{2} − r_{j}^{2} }
C^{i} = { p_{0} ∈ 𝔼^{n} | for all j ≠ i, |p_{0} − p_{i}|^{2} − r_{i}^{2} ≥ |p_{0} − p_{j}|^{2} − r_{j}^{2} }

The set C_{i} is the closed extended nearest point Voronoi region of points p_{0} whose power, |p_{0} − p_{i}|^{2} − r_{i}^{2} with respect to p_{i} is less than or equal to the power of any other point of the configuration with respect to p_{i}. There is a good discussion of how this decomposition fit into the kind of problems that we are considering in [12] by Edelsbrunner. The set C^{i} is often called the extended farthest point Voronoi region of points and there is a good discussion of this in [23] by Seidel.

We now restrict each of the sets by intersecting them with a ball of radius r centered at p_{i}.

C_{i}(r) = C_{i} ∩ B(p_{i}, r)
C^{i}(r) = C^{i} ∩ B(p_{i}, r)

We will call the sets {C_{i}}_{i=1}^{N} and {C^{i}}_{i=1}^{N} the nearest and farthest point Voronoi cells, respectively. We shall be interested especially in the collections {C_{i}(r_{i})}_{i=1}^{N} and {C^{i}(r_{i})}_{i=1}^{N}, which we call the nearest and farthest point truncated Voronoi cells. Figure 1 shows some examples of these sets in the plane.

Figure 1

For each i ≠ j let W_{ij} = C_{i} ∩ C_{j} and W^{ij} = C^{i} ∩ C^{j}, and for any p_{0} ∈ 𝔼^{n} and r > 0, define W_{ij}(p_{0}, r) = W_{ij} ∩ B(p_{0}, r) and W^{ij}(p_{0}, r) = W^{ij} ∩ B(p_{0}, r).

The W_{ij} and W^{ij} are the walls between the nearest point and farthest point Voronoi cells. Note that some of the walls may be empty or low-dimensional, but in any case the walls lie in a hyperplane of dimension n − 1. Define the following for r = (r_{1}, r_{2}, …, r_{N}):

X_{n}(p, r) = ⋃_{i=1}^{N} B(p_{i}, r_{i}), X^{n}(p, r) = ⋂_{i=1}^{N} B(p_{i}, r_{i}).

We need the following easily verified properties of these Voronoi diagrams. We will use Bdy[X] to denote the boundary of a set X in 𝔼^{n}.

(i.) {C_{i}(r_{i})}_{i=1}^{N} is a tiling of X_{n}(p, r) and {C^{i}(r_{i})}_{i=1}^{N} is a tiling of X^{n}(p, r).

(ii.) Bdy[X_{n}(p, r)] ∩ B(p_{i}, r_{i}) = Bdy[X_{n}(p, r)] ∩ C_{i}(r_{i}) and

Bdy[X^{n}(p, r)] ∩ B(p_{i}, r_{i}) = Bdy[X^{n}(p, r)] ∩ C^{i}(r_{i}). (iii.) W_{ij}(p_{i}, r_{i}) = W_{ij}(p_{j}, r_{j}) and W^{ij}(p_{i}, r_{i}) = W^{ij}(p_{j}, r_{j}). (iv.) When W_{ij}(p_{i}, r_{i}) ≠ ∅, the vector p_{j} − p_{i} is a positive scalar multiple of the

outward pointing normal to the boundary of C_{i}(r_{i}) at W_{ij}(p_{i}, r_{i}). Similarly, when W^{ij}(p_{i}, r_{i}) ≠ ∅, the vector p_{j} − p_{i} is a negative scalar multiple of the

outward pointing normal to the boundary of C^{i}(r_{i}) at W_{ij}(p_{i}, r_{i}).

So we get the following.

Lemma 2. For r ≤ s, W_{ij}(p_{i}, r) ⊆ W_{ij}(p_{i}, s), and W^{ij}(p_{i}, r) ⊆ W^{ij}(p_{i}, s).

4. Integral formulas.

One of the key ideas to prove Theorem 1 is a relation between the surface volume of the union (and intersection) of the higher-dimensional balls and the area of the union (and intersection) of lower dimensional disks. First we state a lemma from calculus.

Lemma 3. Let X be a compact integrable set in 𝔼^{n+2} that is a solid of revolution about 𝔼^{n}. In other words the projection of X ∩ {𝔼^{n} × {(s cos θ, s sin θ)} into 𝔼^{n} is an integrable set X(s) independent of θ. Then

Vol_{n+2} [X] = 2π ∫_{0}^{∞} Vol_{n} [X(s)] s ds.

We specialize to the case when the set X is the intersection of a ball of radius r, and half-spaces whose boundary is orthogonal to 𝔼^{n}.

In the following p is a configuration of points in 𝔼^{n} ⊂ 𝔼^{n+2}. We are especially interested in the relation of the volume of C_{i}(r) = C_{i}(r, n) and C^{i}(r) = C^{i}(r, n) in 𝔼^{n} to the volume of the corresponding truncated Voronoi cell C_{i}(r, n + 2) and C^{i}(r, n + 2) in 𝔼^{n+2}.

Lemma 4. If p is a configuration of points in 𝔼^{n} ⊂ 𝔼^{n+2}, then

Vol_{n+2} [C_{i}(r, n + 2)] = 2π ∫_{0}^{r} Vol_{n} [C_{i}(s, n)] s ds
Vol_{n+2} [C^{i}(r, n + 2)] = 2π ∫_{0}^{r} Vol_{n} [C^{i}(s, n)] s ds

Proof. It is clear, in both cases, that C_{i}(r, n + 2) and C^{i}(r, n + 2) are compact sets of revolution. Let B^{n+2}(p_{i}, r) denote the closed ball of radius r in 𝔼^{n+2}. Then B^{n+2}(p_{i}, r)∩ \{𝔼^{n} × \{(s cos θ, s sin θ)\} is an n-dimensional ball of radius \sqrt{r^{2} − s^{2}} in a translate of 𝔼^{n}, and thus by Lemma 3 we have that

Vol_{n+2} [C_{i}(r, n + 2)] = 2π ∫_{0}^{r} Vol_{n} [C_{i}(\sqrt{r^{2} − s^{2}}, n)] s ds.

But if we make the change of variable u = \sqrt{r^{2} − s^{2}}, we get the desired integral. A similar calculation works for C^{i}(r, n + 2).

Applying the fundamental theorem of calculus we get the following.

Corollary 6. We have

\frac{d}{dr} Vol_{n+2} [C_{i}(r, n + 2)] = 2πrVol_{n} [C_{i}(r, n)] , and
\frac{d}{dr} Vol_{n+2} [C^{i}(r, n + 2)] = 2πrVol_{n} [C^{i}(r, n)] .

Remark 2. We can interpret \frac{d}{dr} Vol_{n+2} [C_{i}(r, n + 2)], evaluated at r = r_{i}, as the (n+1)- dimensional surface volume of Bdy[X_{n+2}(p, r)] ∩ C_{i}(r_{i}, n + 2), since the radius vector for the ball is orthogonal to that part of the boundary of C_{i}(r_{i}, n + 2). We can make a similar identification for Bdy[X^{n+2}(p, r)] ∩ C^{i}(r_{i}, n + 2).

5. Csikós’s formula.

Suppose that p(t) = (p_{1}(t), …, p_{N}(t)), for 0 ≤ t ≤ 1, is a smooth motion of the configuration p = p(0) in some Euclidean space 𝔼^{n}. Let d_{ij} = |p_{i}(t) − p_{j}(t)|, and let d′_{ij} be the t-derivative of d_{ij}. Then Csikós’s Theorem 4.1, for unions of balls, in [10] is the following. For intersections of balls, we indicate the appropriate adjustments.

Theorem 2. Let n ≥ 2 and let p(t) be a smooth motion of a configuration in 𝔼^{n} such that for each t, the points of the configuration are pairwise distinct. Then regarding the following as functions of t, V_{n}(t, r) = Vol_{n}[X_{n}(p(t), r)] and V^{n}(t, r) = Vol_{n}[X^{n}(p(t), r)] are differentiable and,

\frac{d}{dt}V_{n}(t, r) = ∑_{1≤i<j≤N} d′_{ij}Vol_{n−1}[W_{ij}(p_{i}(t), r_{i})],

\frac{d}{dt}V^{n}(t, r) = ∑_{1≤i<j≤N} −d′_{ij}Vol_{n−1}[W^{ij}(p_{i}(t), r_{i})].

Proof. For the case of unions of balls, this is the same result as in [10]. For the case of intersections, the proof proceeds in a very similar way, but when one uses property (iv.), there is a sign change.

The following is a result in [15] of Kirszbraun. There are other simple elementary proofs, for example in [17] as described by Klee and Wagon and described by Alexander in [2]. It is immediate from Theorem 2 and Lemma 1, which was also pointed out by Alexander.

Corollary 7. If the configuration p is a contraction of the configuration q in 𝔼^{n}, and ⋂_{i=1}^{N} B(q_{i}, r_{i}) is non-empty, then ⋂_{i=1}^{N} B(p_{i}, r_{i}) is non-empty as well.

6. Expanding the configuration.

In order to get a global relation between the (n+1)-dimensional volume of the surface of our sets in 𝔼^{n+2} and the n-dimensional volume of our sets in 𝔼^{n}, we consider a particular deformation of just the radii, fixing the configuration p. For each i = 1, 2, …, N and 0 ≤ s, define r_{i}(s) = \sqrt{r_{i}^{2} + s}. Each r_{i} is constant, and the function r_{i}(s) is independent of the parameter t. We assume that each r_{i} > 0. Then we calculate that

(4)  \frac{d}{ds}r_{i}(s) = \frac{1}{2r_{i}(s)}.

Now define r(s) = (r_{1}(s), …, r_{N}(s)), and regard Vol_{n}[X_{n}(p(t), r(s))] = V_{n}(t, s) and Vol_{n}[X^{n}(p(t), r(s))] = V^{n}(t, s) as functions of both variables t and s. Throughout we assume that all r_{i} > 0.

Lemma 5. Let the motion of the configuration p(t) be at least continuously differentiable. Then the functions V_{n}(t, s) and V^{n}(t, s) are continuously differentiable in t and s simultaneously, and for fixed t, the extended nearest point and farthest point Voronoi cells are constant.

Proof. Recall that a point p_{0} is in an extended Voronoi cell C_{i} or C^{i}, when for all j ≠ i, |p_{0} − p_{i}|^{2} − |p_{0} − p_{j}|^{2} − r_{i}(s)^{2} + r_{j}(s)^{2} is non-positive for C_{i} and non-negative for C^{i}. But r_{i}(s)^{2} − r_{j}(s)^{2} = r_{i}^{2} − r_{j}^{2} is constant. So each C_{i} and C^{i} is constant as a function of s.

Since p(t) is continuously differentiable, then the partial derivatives of V_{n}(t, s) and V^{n}(t, s) with respect to t exist and are continuous. Since the (n−1)-dimensional surface volume of boundaries of X_{n}(p, r(s)) and X^{n}(p, r(s)) are continuous functions of s, the partial derivatives of V_{n}(t, s) and V^{n}(t, s) with respect to s exist and are continuous. Thus V_{n}(t, s) and V^{n}(t, s) are both continuously differentiable with respect to t and s simultaneously.

Note that we now can interchange the order of partial differentiation with respect to the variables t and s. Combining Lemma 5 and Theorem 2, we get the following.

Lemma 6. Let p(t) be a smooth motion of a configuration in 𝔼^{n} such that for each t the points of the configuration are pairwise distinct. Then the following hold:

\frac{∂^{2}}{∂t∂s}V_{n}(t, s) = ∑_{1≤i<j≤N} d′_{ij} \frac{∂}{∂s}Vol_{n−1}[W_{ij}(p_{i}(t), r_{i}(s))],

\frac{∂^{2}}{∂t∂s}V^{n}(t, s) = ∑_{1≤i<j≤N} −d′_{ij} \frac{∂}{∂s}Vol_{n−1}[W^{ij}(p_{i}(t), r_{i}(s))].

Hence if p(t) is expanding, then by Lemma 2, \frac{∂}{∂s}V_{n}(t, s) is monotone increasing in t, and \frac{∂}{∂s}V^{n}(t, s) is monotone decreasing in t.

Bear in mind that we can replace W_{ij}(p_{i}(t), r_{i}(s)) by W_{ij}(p_{j}(t), r_{j}(s)) in the terms above by property (iii.).

Let K_{i}(p, r) and K^{i}(p, r) be the (n−1)-dimensional surface volume of Bdy[X_{n}(p, r)]∩ C_{i} and Bdy[X^{n}(p, r)] ∩ C^{i} respectively. Then we observe the following, using Property (ii.).

Theorem 3. We can interpret \frac{∂}{∂s}V_{n}(t, s) and \frac{∂}{∂s}V^{n}(t, s) evaluated at r = r(0) as

\frac{1}{2} ∑_{i=1}^{N} K_{i}(p, r)/r_{i} and \frac{1}{2} ∑_{i=1}^{N} K^{i}(p, r)/r_{i},

the weighted (n − 1)-dimensional volume of the boundary of X_{n}(p, r) and X^{n}(p, r) respectively. Thus under smooth expanding motions, these boundary volumes are monotone functions.

For smooth motions this generalizes the result in [5] of Bollobás for the plane as well as Csikós’s other proof in [11] for not necessarily congruent disks in the plane. See Section 8 for comments, however.

7. Proof of Theorem 1.

We now specialize to the case when the configuration is in 𝔼^{n}, but the motion occurs in 𝔼^{n+2}. So we wish to connect the volumes of Vol_{n}[X_{n}(p, r(s))] = V_{n}(p, r(s)) and Vol_{n}[X^{n}(p, r(s))] = V^{n}(p, r(s)) in 𝔼^{n} to the corresponding volumes V_{n+2}(p, r(s)) and V^{n+2}(p, r(s)) in 𝔼^{n+2}.

Lemma 7. Let p = (p_{1}, …, p_{N}) be a fixed configuration in 𝔼^{n} ⊂ 𝔼^{n+2}. Then

\frac{d}{ds}V_{n+2}(p, r(s)) = πV_{n}(p, r(s)), and
\frac{d}{ds}V^{n+2}(p, r(s)) = πV^{n}(p, r(s)).

Proof. By Property (i.), V_{n+2}(p, r(s)) = ∑_{i=1}^{N} Vol_{n+2} [C_{i}(r_{i}(s), n + 2)]; applying Corollary 6, the chain rule, and (4) we have that

\frac{d}{ds}V_{n+2}(p, r(s)) = ∑_{i=1}^{N} \frac{d}{ds}V_{n+2}(C_{i}(r_{i}(s), n + 2))

= ∑_{i=1}^{N} \frac{d}{dr_{i}(s)}V_{n+2}(C_{i}(r_{i}(s), n + 2))\frac{dr_{i}(s)}{ds}

= ∑_{i=1}^{N} 2πr_{i}(s)V_{n}(C_{i}(r_{i}(s), n)) (\frac{1}{2r_{i}(s)})

= πV_{n}(p, r(s)).

Similarly \frac{d}{ds}V^{n+2}(p, r(s)) is calculated.

We are now in a position to show our main result.

Proof of Theorem 1. Suppose that the configuration q = (q_{1}, …, q_{N}) is an expansion of the configuration p = (p_{1}, …, p_{N}) in 𝔼^{n}. By assumption, there is a piecewise-smooth expansion p(t) = (p_{1}(t), …, p_{N}(t)), for 0 ≤ t ≤ 1, in 𝔼^{n+2} such that p(0) = p, and p(1) = q. So there is a finite number of sub-intervals of [0, 1], where each pair of points is distinct or remain coincident. In either case, in the interior of each interval, by Lemma 6 applied to 𝔼^{n+2}, we conclude that \frac{d}{ds}V_{n+2}(p(t), r(s)) is increasing in t. By taking limits as t approaches the endpoints of each interval, we have that \frac{d}{ds}V_{n+2}(p(t), r(s)) is increasing for all 0 ≤ t ≤ 1. Applying Lemma 7, πV_{n}(p(0), r(s)) = \frac{d}{ds}V_{n+2}(p(0), r(s)) ≤ \frac{d}{ds}V_{n+2}(p(1), r(s)) = πV_{n}(p(1), r(s)). Evaluating when s = 0, we get the desired result. A similar argument shows that V^{n}(p(0), r) ≥ V^{n}(p(1), r).

Proof of Remark 1. Here the motion of the configuration p(t) is in 𝔼^{m}, but the dimension of the affine span is at most n + 2 and the the dimension of the span of p(t) is piecewiseconstant. On each interval, while the dimension is constant, it is possible to continuously, smoothly define an orthonormal coordinate system, whose dimension is the dimension of the affine span of the configuration p(t). If the dimension of the affine span is less than n+ 2, define additional coordinates so that there is always an (n+2)-dimensional coordinate system during the interior of each of the time intervals. For sufficiently small subintervals of these intervals, the proof of Theorem 1 applies to these coordinate systems. So the (n + 1)-dimensional weighted volume of the boundary changes monotonically as before. Then Lemma 7 applies, and we get the desired result.

8. Examples and comments. Theorem 3 is delicate. If the configuration q is an expansion of p but not a continuous expansion, then even in the plane with disks of the same radius, the length of the boundary of the union of disks may not be larger for q than for p. The example in Figure 2, due to Habicht and Kneser, described in [17], shows this in the plane.

Figure 2

Except for a small portion of its boundary, the inner shaded region is covered by a large number of congruent disks. Then for a large k, there are k disks that are arranged on the boundary as indicated. This is the configuration p. Then some of the inner disks are moved radially outward covering almost all of the old boundary, leaving behind enough disks to still almost cover the original union. This is the expanded configuration q, and the associated disks almost cover the boundary of the disks about p, but now the boundary is almost a perfect circle. The ratio of the length of the boundary of the union of the disks about q to the length of the boundary of the union of the disks about p approaches π/2 > 1. We do not know how to get a better ratio in the plane. This example extends to higher dimensions.

If we have incongruent disks in the plane and a smooth motion, it can happen that the (unweighted) length of the boundary of the union can decrease while the configuration is expanding. The following example is very similar to the one described in [3] by Bern.

Figure 3

The smaller disk moves as indicated, which is clearly a smooth expansion of the three centers. The shaded triangular region Δ, whose shape is close to an actual triangle, represents the additional area. Two of the sides of Δ vanish as part of the boundary of the union of the disks, and the third side is the new part of the boundary. The triangle inequality implies that the length of the boundary decreases as the smaller circle moves. Note that two of the circles are the same length, and by choosing the two equal circles sufficiently close to each other, this example will work when the radius of third disk is arbitrarily close to the radius of the other two.

We are still left with the question as to what happens for volumes of expansions of unions and intersections of balls in higher dimensions. It is possible that an extension of Lemma 6 could help. We finish with the following comment.

Remark 3. If the following inequalities hold for k for a sufficiently smoothly expanding configuration p(t) in 𝔼^{4k}, then Conjecture 1 and Conjecture 2 hold in 𝔼^{2k}.

\frac{∂^{k+1}}{∂t(∂s)^{k}} V_{n}(t, s) = ∑_{1≤i<j≤N} d′_{ij} \frac{(∂)^{k}}{(∂s)^{k}} Vol_{n−1}[W_{ij}(p_{i}(t), r_{i}(s))] ≥ 0,

\frac{∂^{k+1}}{∂t(∂s)^{k}} V^{n}(t, s) = ∑_{1≤i<j≤N} −d′_{ij} \frac{(∂)^{k}}{(∂s)^{k}} Vol_{n−1}[W^{ij}(p_{i}(t), r_{i}(s))] ≤ 0.

References

1. R. Alexander, Lipschitzian mappings and total mean curvature of polyhedral surfaces, no., I. Trans. Amer. Math. Soc. 288 (1985), no. 2, 661–678, MR86c:52004.

2. R. Alexander, The circumdisk and its relation to a theorem of Kirszbraun and Valentine, Math. Mag. 57 (1984), no. 3, 165–169, MR85f:52028.

3. M. Bern, Pushing Disks Together, web page http://www.parc.xerox.com/csl/members/ bern/disk.html.

4. M. Bern; A. Sahai, Pushing disks together—the continuous-motion case, Discrete Comput. Geom. 20 (1998), no. 4, 499–514, MR99i:520.

5. B. Bollobás, Area of the Union of Disks, Elemente der Mathematik 23 (1968), no. 4, 60–61, MR38 #3772.

6. G. Bouligand, Ensembles impropres it nombre dimensional, Bull. Sci. Math. 52 (1928), 320–344.

7. V. Capoyleas, On the area of the intersection of disks in the plane, Comput. Geom. 6 (1996), no. 6, 393–396, MR98b:52003.

8. V. Capoyleas; J. Pach, On the perimeter of a point set in the plane, Discrete and computational geometry (New Brunswick, NJ) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Amer. Math. Soc., Providence, RI, 6 (1991), 67–76, MR92k:52013.

9. H. T. Croft; K. Falconer; R. K. Guy, Unsolved problems in geometry, Springer-Verlag, New York (1991), MR92c:52001.

10. B. Csikós, On the volume of the union of balls, Discrete Comput. Geom. 20 (1998), no. 4, 449–461., MR99g:52008.

11. B. Csikós, On the Hadwiger-Kneser-Poulsen conjecture, Intuitive geometry, Bolyai Soc. Math. Stud., 6, János Bolyai Math. Soc., Budapest, (1995), 291–299, MR99g:52008.

12. H. Edelsbrunner, The union of balls and its dual shape, Discrete Comput. Geom. 13 (1995), no. 3-4, 415–440, MR96a:52020.

13. M. Gromov, Monotonicity of the volume of intersections of balls, Geometrical aspects of functional analysis 85–86, Lecture Notes in Math., Springer, Berlin (1987), no. 1267, 1–4, MR89b:58075.

14. H. Hadwiger, Ungelöste Probleme No. 11, Elem. Math. 11 (1956), 60-61.

15. M. D. Kirszbraun, Über die zusammenziehenden und Lipschitzsche Transformationen, Fundamenta Mathematicae 22 (1934), 77-108.

16. V. Klee, Some unsolved problems in plane geometry, Math. Mag. 52 (1979), no. 3, 131–145, MR80m:52006.

17. V. Klee, V.; S. Wagon, Old and new unsolved problems in plane geometry and number theory, 11. Mathematical Association of America, Washington, DC, The Dolciani Mathematical Expositions (1991), 16-20, 86-90, 274-278, MR92k:00014.

18. M. Kneser, Einige Bemerkungen über das Minkowskische Fläschenmass, Arch. Math. 6 (1955), 382–390, MR17,469e.

19. M. Meyer; S. Reisner ; M. Schmuckenschläger, The volume of the intersection of a convex body with its translates, Mathematika 40 (1993), no. 2, 278–289, MR94m:52009.

20. W. Moser; J. Pach, Research Problems in Discrete Geometry, Preprint, Department of Mathematics and Statistics, McGill University, Montreal, Canada, RPDG#39 (1987).

21. E. T. Poulsen, Problem 10, Mathematica Scandinavica 2 (1954), 346.

22. W. Rehder, On the volume of unions of translates of a convex set, Amer. Math. Monthly 87 (1980), no. 5, 382–384, MR81g:52004.

23. R. Seidel, Exact upper bounds for the number of faces in d-dimensional Voronoi diagrams, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Amer. Math. Soc., Applied geometry and discrete mathematics 4 (1991), 517–529, MR93b:52010.

24. V. N. Sudakov, Gaussian random processes, and measures of solid angles in Hilbert space, (Russian), Dokl. Akad. Nauk SSSR 197 (1971), 43–45, MR#6027.

25. F. A. Valentine, Convex sets, Reprinting of the 1964 original, Robert E. Krieger Publishing Co., Huntington, N.Y., MR#14306.

Eötvös University Department of Geometry H-1053 Budapest Kecskeméti utca 10-12 Hungary

E-mail address: kbezdek@ludens.elte.hu

Department of Mathematics Malott Hall Cornell University Ithaca, NY 14853 USA

E-mail address: connelly@math.cornell.edu