Pushing Disks Together
In 1954 and 1955 Kneser and Thue Poulsen asked the following question:
if you have a collection of unit disks in the plane
and you move the disks so that each center-center
distance decreases, must the area of the union also decrease?
(Throughout this article, we use "decrease"
in the weak sense of "does not increase".)
This problem is still open.
A special case of the problem, in which center-center distances
decrease continuously, was answered affirmatively
by Bollobas [2] in 1968.
This "continuous-motion" result has
been generalized to disks of arbitrary radii [1,4]
and to balls of arbitrary radii in higher dimensions [5].
The answer is also known to be "yes" for
d+1 balls in d dimensions-- in fact, this case can
be reduced to the continuous-motion case-- and in the limit
of very large equal-radius disks in two dimensions [3].
The question can also be asked in a "dual" form:
must the area of the intersection increase?
The answer is known to be "yes" in the continuous-motion case.
The general case, even for just 4 diks,
cannot be reduced to the continuous-motion case
as shown by the example below.
A related question asks about the length of the perimeter.
For continuous-motion unit disks, the perimeter
of the union must decrease [2] and the perimeter
of the intersection must increase.
For continuous-motion disks of arbitrary radii, however,
the perimeter of the union can either decrease or increase
(see the two examples below).
Without the continuous motion assumption,
the perimeter of the union of unit disks can increase or decrease,
the same question about the intersection seems to be open.
Lastly, doing away with the disks and just keeping
their centers, it is known that the perimeter of a
point set (that is, the perimeter of its convex hull)
must decrease [3].
Finally, since the exact problems seem to be so hard,
one can ask for approximation bounds.
Kneser (see [6]) proved a bound of 9 (more generally, 3^d in
d dimensions) for the original question, meaning
that the area of the union of unit disks
can increase by at most a factor of 9.
Interestingly, there is no
appromixation bound known for the dual question concerning the
area of the intersection of unit disks, or for
either the original or dual questions for
disks of arbitrary radius.
[1] M. Bern and A. Sahai. Pushing disks together-- the
continuous motion case. In
Proc. 28th Symp. Theory of Computing, 1996.
[2] B. Bollobas. Area of the union of disks.
Elemente der Mathematik 23 (1968) 60-61.
[3] V. Capoyleas and J. Pach. On the perimeter of
a point set in the plane. In Discrete and Computational
Geometry, DIMACS Series in Disc. Math. and Theoretical
Computer Science, Vol. 6, 1991, 67-76.
[4] B. Csikos. On the Poulsen Kneser Hadwiger conjecture.
To appear in Intuitive Geometry,
Colloquia Mathematica Societatis J. Bolyai, 1996.
[5] B. Csikos. On the volume of the union of balls. Manuscript, 1996.
[6] V. Klee and S. Wagon. Old and New Unsolved Problems
in Plane Geometry and Number Theory, Mathematical
Association of America, 1991.
This page updated September 1998 / bern@parc.com