A worm is one unit long, has no width, and can be in any position (coiled, overlapping, straight, etc.) You must design a shape to cover (able to place on top of worm and completely cover it: two dimensional) all possible worms (all are 1 unit long)using the least amount of material for covering the worms(the area of the cover should be as small as possible). Keep in mind that the worm has no width (only has length), so you don`t have to worry about that. What shape has the smallest area that will cover a worm in any position? What is the area of that shape?


I first thought of a circle with a diameter of 1 unit, but realized that the area (pi/4) was too large. I then thought about a square with a diagonal of 1 unit and then a triangle with a height of 1 unit, or a base of 1 unit (though I`m not sure if this shape could cover a worm in any position). Then I thought of a triangle that has a hypotenuse of 1 unit in length. The hypotenuse itself would cover a straight worm, and if there were ONE 90 degree bend in the worm, the long side of the worm could be along the hypotenuse and the short side would turn and go to one of the short sides.

Maybe a triangle that is 1 unit on the longest side, and which has two equal sides with a right triangle between them for the other two sides would work. Your prompt help would be greatly appreciated.

I'll have to think about this, but my immediate intuition is that it will involve curved edges, except for one straight one, not triangles. Any ideas anyone...

On second thoughts, I think it probably will be a triangle, not a symmetric one though, start with a height of length 1 and on one side allow for the worm to be bent in that direction and on the other side allow for the worm to be bending in both directions, this scond side will be smaller.

Sean,
I don't quite understand the triangle you described. Is the height 1 and the base 2? Isn't that too big?

The only idea I had was to first discretize the worm so that it consists of N straight bits of length (1/N) .
1. Guess a shape that's too small
2. Generate N random points, and form the shape you get with these points linked in order.
3. Get a cool computer program to see if the worm can fit your shape- if not extend the shape as little as possible so as to allow fitting.
4. Repeat
let N get big and leave your Cray multi-system running a few days to get an 'answer'

I'm not convinced this works at all but that's about all I have I'm afraid.

not a bad idea, although I think there may be a problem in 3, as it will always be ambiguous how to extend the existing shape in the optimal way, in particular you may end up in a local minimum that isn't the absolute minimum. What you have certainly pointed out is that this problem is highly non-trivial, I wonder is there is a nice answer...

If I remember correctly, this problem is mentioned in Game, Set and Maths by Ian Stewart. Unfortunately that is one of the books that I decided to leave at home this term. I believe that the answer Stewart came up with was a semicircle, probably of diameter 1. I'll see if I can come up with a decent justification of that - I'm pretty sure it will cover any worm, but not so sure that it is optimal.

I think that this was an unsolved research problem last year, so it's probably still open. If anyone has any ideas then they might be publishable.

One approach that has been tried involves insisting that the worm must lie on a square grid, and then making a finer and finer grid which is a closer and closer approximation to the continuous case. Using this approach it's not hard to find something better than the semicircle.

But what is the shape you get that is better than the semicircle? Also, you can't rotate the worm if it's on a grid, so you are not guaranteed to find the best shape using this method. The only other way I've thought of for attacking this question is to define some class of curves (for instance, the curve q(a) is a horizontal line of length 1/2 followed by another line of length 1/2 at angle a). The next stage of the method is to find the shape of minimum area that works for your chosen class of curves. Finally, you hope that you can show that this shape can in fact hold any curve of length 1. If you do this then you must have the answer, because the shape must be able to at least hold the curves that you've defined. That approach led me to suspect that the answer is in fact a semicircle, but I haven't proved it. Has anyone managed to prove that the semicircle can hold any length 1 curve? Can anyone find the minimum area shape for some class of curves (e.g. the ones I listed above)?

Actually, since any finite length curve can be uniformly approximated on an appropriate grid, a limiting process based on this idea would give an answer. There are two problems with this. One is how to define the limiting process, since there may not be a unique minimum at each stage. I think that it is possible to get round this, but possibly at the expense of guaranteeing global minimality. The second is rather more serious and concerns turning the theoretical process into a practical program. However, it is one reasonable way to investigate the problem which, I understand, several researchers have already tried.

Apologies to all those for whom the above is gibberish.

Jonathan

Yes, but how does this process allow for the worm to be rotated, unless you allow for this you're going to end up with a circle which is certainly not minimal.

Incidentally, if anyone knows about such things, this seems an appropriate circumstance to use a genetic algorithm to avoid local (but not absolute) minima. You encode difference shapes as "genes", see how different shapes perform when tried against different worm configurations, keep the best few (natural selection) and then cross their genes to get a new load of shapes similar to the previous ones.

So are we abandoning hope of an analytic solution?

I like the idea of a genetic algorithm, but how would you (a) represent an arbitrary shape using genes, and (b) cross these shapes in such a way that some properties of the shape is carried forward? I'm not yet abandoning hope of an analytic solution, but these methods might be useful to find some contenders for the throne.

Here is one way of looking at the problem, based on what I wrote above. Consider instead a worm of length n which can only lie on a grid of unit squares. The blanket must be made from the squares too. Divide the lengths by n to get an approximation to the continuous problem. As the blanket can be rotated, there is no need to consider rotation of the worm separately.

The following shapes are the best possible for n up to 4 with X representing a square.

X

XX

XX
X
X

or

X
XX
X

XXXX
X

or

X
XX
X
X

These have scaled areas 1, 1/2, 4/9, 5/16. This last one is smaller then the area of the semicircle, but it's not a solution to the same problem so I haven't proved that it's better.

I don't have time to do more now, but I have seen this before somewhere. I think that it's not very hard to prove that any curve can fit inside a semicircle, or a shape a bit like the one below, but I can't see how to do it off the top of my head.

XXX
XXXX
XXXX
XXX
X
X
X
X

As I said before, this is known to be a hard research problem so we're not very likely to crack it - that's not a reason to stop trying though! (although exam revision probably is.)

Jonathan

I have a proof that a semicircle of diameter 1 covers all unit worms:

For any worm, draw a rectangle around it. The width w of the rectangle will lie between 0 and 1. The height h of the rectangle will be at worst ½(1-w² )^½ , which occurs when the worm forms 2 sides of an isoceles triangle with base w. We therefore have a group of rectangles which will cover any worm with a given width. Lay these rectangles on top of each other and we get a semicircle, which can therefore cover any unit worm.

In fact that argument can be extended to give an improvement on the semicircle. For rectangles with h> w we may rotate them through 90° before adding them to our shape. We will then get a semicircle with the top part missing. The rectangle is square for w=h=1/sqrt(5), and so the cropped semicircle has height 1/sqrt(5).

The cropped version has area 0.377 or thereabouts, rather than the semicircle's 0.393.

good that we have some analytic results.

On the numerical front, a genetic algorithm would work on the discretised problem as:

a) start with a number of shapes defined genetically by a string of 1s and 0s, one for each point of the discretised grid.

b) pick a worm at random. Do any of the chosen shapes cover it (allowing for rotations, so perhaps the discretisation should be cylindrically symmetric, not squre based)? If some do or nearly do (i.e. are only out by a few points) then this are retained and the others are "killed".

c) we then "cross" the remaining shapes (i.e. take their genetic code half-half or something) and allow random mutations.

d) repeat

This process will give improving shapes, the point of crossing is that it can help avoid local minima (indeed this is why it occurs in nature). It is not actually too difficult to implement the above, and if someone isn't to bothered about their exams (not me I'm afraid) they might want to try.

Sean

Nice proofs, I think this method can be extended even further though. I haven't yet done this (I had a look at it, but my brain isn't on top form at the moment as I'm doing Statistics work. Take an arbitrary curve of length 1, rotate it so that the projection of the curve onto the x-axis has minimum length, call this length w. Now, translate the curve so that at the lowest point it touches the x-axis, and so that at the point of minimum x is just touches the y-axis and at the point of maximum x is just touches the line x=w. Now, if you project the curve onto any line, the length of that projected line must be less than or equal to w (by definition of w). I think that this should define a shape which the transformed curve must be inside. Now we have a group of shapes depending on parameter w (which certainly can't be as large as 1, but I'm not sure what the upper bound will be, I think it'll be greater than or equal to 1/sqrt(2) though). We now overlap these shapes in the most efficient way (it'll probably be obvious from the shapes what that is), and we'll have a shape at least as good as the cropped semicircle, hopefully better.

I hope that made sense, I'll post again when I'm entirely sure what I'm saying...

Has anyone managed to find a lower bound for the problem? My initial reaction was that the answer to this question could be zero - i.e. it may be possible to find a sequence of shapes that fulfil the requirement whose area tends to zero. Can anyone prove this wrong?

Yours,

Michael

At the moment, everyone on the NRICH team is in exam term, so nobody has an enormous amount of time to think about difficult questions like this. We might get a bit further later on (my exams finish on the 9th June, others will finish around this time I expect).

I'm not sure we can assume it's convex. Some asymmetry involving nonconvexity might be useful.

Do you think that we can restrict the question to ensure the shape is 'nice' and doesn't have any holes in it - is 'simply connected' the correct technical term for what I mean here?

If so, then the shape certainly has to contain the circle descibed by Dan, in which case p /4 will be a lower bound.

If we do not allow ourselves this restriction then I think everything will be much more unpleasant. Most significantly, we may have to worry about what we mean by the 'area' of a arbitrary shape, and we might have to use measure theory and stuff like that. But I'm certainly not an expert on things like this so maybe someone who is could shed some more light on the matter.

James.

I can't see any a priori reason to assume it is simply connected (no holes). Certainly I think an analytic solution will be very hard, if at all possible, although I do think it reasonable to assume the shape will be reasonable enough not to need weird measure-theoretic ideas.

I was kind of assuming that we weren't restricted to "nice" shapes which are being called convex as otherwise won't we get lots of wasted space in the middle? I thought that maybe, if we let f(x,y) return 1 when co-ordinates (x,y) are part of the shape and 0 when (x,y) is not part of the shape then the area could be thought of as the Lesbegue integral of f(x,y) over the area. (I've heard of this from discussions in the One to One and Open Discussions area.)

So if we simply draw all possible worms on top of each other on a sheet of paper, then maybe it is possible to work out the minimum value of the Lesbegue integral of f(x,y), and this may have some relevance to the original problem. This minimum would come about when the worms were arranged efficiently on top of each other, i.e. part of several worms cover the same space. But I'm really not sure how to do this.

Yours,

Michael

I wasn't suggesting that the optimal solution to the original problem would be in any way 'nice'. I was proposing this assumption as a different interpretation of the original question - making a different, but, I imagine, simpler question to solve. Almost certainly these two questions have different answers.

If you do not have any assumptions about the class of permissible shapes, then it's not so much a matter of needing wierd measure-theoretic ideas to solve the problem, but of needing weird measure-theoretic ideas to describe the problem.

James.

If we assume the shape to be connected, then we don't need any weird measure theory ideas I don't think, and it is easy to show that the shape must be connected (if it wasn't, just translate the two disconnected parts to overlap, reducing the area).

Although, if there were an infinite number of small shapes of zero area then the above reasoning wouldn't hold. I don't think this is a problem, because you can't fit enough shapes of zero area in a plane to cover all possible worms. For instance, any curve is a shape of zero area, cover the plane with every possible curve (the shape is unbounded of course), this will have zero area and accomodate every worm. Unfortunately, you can't fit all the curves into the plane in this way. Seeing why this is true is quite easy, just construct an uncountable number of ellipses and try and tile the plane so that none intersect. You can't do it. Well, I know this isn't a solid proof that the shape is connected, but I think we can assume that it is. I don't think we can assume simply connected though. My intuition leads me to think that the shape is going to be EITHER nice and simply described OR a bizarre construction which allows you to make the area smaller than any given epsilon > 0.

Okay, here at the best known results to date (I think!)

If we consider only convex covering shapes then the area lies between the following:

0.2194626846 and 0.27524

These are due to Schaer+Wetzel (in the 70s) and Poole+Gerriets+Norwood+Laidacker (in the 70s and 90s).

If we get rid of the convexity requirement then Davies (in the 60s) constructed sets of measure 0 (ie. 0 area) which cover all polygonal worms. However, Marstrand (in the late 70s) proved that a cover for all rectifiable arcs (ie. ones where length makes sense) must have strictly positive measure.

Have just seen that the lower bound mentioned above can be improved to:

(4+sqrt(3))/24 ~ 0.2388354503

this was done by Ferguson in March 2000.

AlexB.

I just got a very comprehensive email on this subject, here is a copy:

---

Quote:

See Chapter 7 ("Besicovitch and Kakeya sets") of Falconer [5],
especially 7.4: "Generalizations" on pp. 106-109. For instance,
Theorem 7.9 on page 103 says that any subset of R^2 containing a
line in every direction must have Hausdorff dimension 2. The
result is due to Davies [4], who proved the slightly stronger
result that any subset of R^2 containing a line segment in every
direction (there does not have to be a positive lower bound on the
lengths of these segments) must have Hausdorff dimension 2.
(Indeed, as Falconer points out, if dim(E) < 2,then E intersects
all lines, in all but a 1-measure zero set of directions, in a set
of 1-measure zero.) I believe it is still an unsolved problem,
the Kakeya Conjecture, as to whether there exists a set in R^n
(n > 2) with n-measure zero containing a line segment in every
direction. [See Bourgain [2], Green [11], and Wolff [9] [17] for
some recent work on this question.]

In the opposite direction Besicovitch (1919) constructed a compact
set in R^2 with 2-measure zero containing a line segment in every
direction. Various similar results have been proved over the
years. For example, Davies [4] constructed a set in R^2 of
2-measure zero containing a translate of every polygonal arc,
and Marstrand [7] constructed in each R^n a set of Hausdorff
dimension 1 containing every congruent copy of any preassigned
countable collection of lines. [Keep in mind that there are
continuum many such congruent copies when n > 1.]

Marstrand [8] proved that given any n-measure zero set E in R^n
(n > 1), there exists a C^infinity curve of length one having
no congruent copy in E. Note that any C^infinity curve--indeed,
any C^1 curve--is rectifiable. [In fact, Marstrand proves that
every non-empty open connected subset D of R^n contains a
C^infinity curve which cannot be transformed into a subset of
E by an invertible analytic mapping from D into R^n.] Falconer [5]
(bottom of page 107) mentions this as solving the 'worm problem',
although Marstrand [8] doesn't appear to use this term. It seems
that the term 'worm problem' is due to Leo Moser. See Finch [10]
for more on the worm problem. Finch gives 36 references, many of
which are not among those I give below.

A helpful beginning expository paper is Cunningham [3]. Thomas
Wolff (CalTech) has recently written several papers on these
matters. Of these papers, I would recommend looking at
Wolff [9] [17], which contains 58 references. Other papers
that might be of interest are Bourgain [2] and Green [11].

For the Baire category analog of a Nikodym set, see Bagemihl
and Humke [1], Humke [6], and Steprans [15].

[1] Frederick Bagemihl and Paul Humke, "Rectifiably ambiguous
points of planar sets", J. Australian Math. Soc. (A) 20)
(1975), 85-109.
[MR 51 #14004; Zbl 305.04005]

[2] J. Bourgain, "On the dimension of Kakeya sets and related
maximal inequalities", Geom. Funct. Anal. 9 (1999), 256-282.
[MR 2000b:42013; Zbl 930.43005]

[3] F. Cunningham, "Three Kakeya problems", Amer. Math. Monthly
81 (1974), 582-592.
[MR 50 #14497; Zbl 286.52009]

[4] R. O. Davies, "Some remarks on the Kakeya problem", Proc.
Cambridge Phil. Soc. 69 (1971), 417-421.
[MR 42 #7869; Zbl 209.26602]

[5] Kenneth J. Falconer, THE GEOMETRY OF FRACTAL SETS, Cambridge
Tracts in Mathematics 85, Cambridge University Press, 1985.
[MR 88d:28001; Zbl 587.28004]

[6] Paul Humke, "Baire category and disjoint rectilinear
accessibility", J. London Math. Soc. (2) 14 (1976), 245-248.
[MR 56 #563; Zbl 342.26005]

[7] J. M. Marstrand, "An application of topological transformation
groups to the Kakeya problem", Bull. London Math. Soc. 4 (1972),
191-195.
[MR 47 #4234; Zbl 248.28017]

[8] J. M. Marstrand, "Packing smooth curves in R^q", Mathematika
26 (1979), 1-12.
[MR 81d:52009; Zbl 403.28008]

[9] Thomas H. Wolff, "Recent work connected with the Kakeya
problem", pp. 129-162 in Hugo Rossi (ed.), Prospects in
Mathematics (Invited talks on the occasion of the 250'th
anniversary of Princeton University, 1996.), American
Math. Society, 1999. (This paper is on-line. See [15].)
[MR 2000d:42010. This was a featured review, which even
non-math-sci-doc members can access at

;

The Zbl review not officially numbered yet, but you can find
it on-line by going to

.]

|---------------------|
| INTERNET REFERENCES |
|---------------------|

[10] Steven Finch, (a) "Moser's Worm Constant", (b) "Results
for Closed Worms", and (c) "Outcomes Corresponding to
Translation Covers".

(a)
(b)
(c)

[11] B. J. Green, "The Kakeya Problem", 78 page expository paper.



[12] Nets Hawk Katz, Izabella Laba, and Terence Tao, "An improved
bound on the Minkowski dimension of Besicovitch sets in R^3",
65 pages, to appear in Annals of Math.



[13] Nets Hawk Katz and Terence Tao, "A new bound on partial
sum-sets and difference-sets, and applications to the Kakeya
conjecture", 6 pages, submitted to Math Research Letters.



[14] Izabella Laba, "An improved bound on the Minkowski dimension
of Besicovitch sets in R^3" and "An improved bound on the
Minkowski dimension of Besicovitch sets in medium dimension".



[15] Juris Steprans, "A category analogue of a Nikodym set", on-line
construction in the link labeled "A partial solution to the
problem" at



[16] Terence Tao, (a) "Bochner-Riesz, Restriction, and Kakeya
estimates" and (b) "Besicovitch sets" [A java applet
giving one version of Besicovitch's construction.], (c) A
very detailed chart showing the relationships between
results and conjectures related to Kakeya and Nikodym sets
[See the link for "interconnections between various
conjectures in this family".], (d) "Restriction theorems and
applications", Lecture Notes for UCLA Math 254B, Spring 1999.

(a,c)
(b)
(d)

[17] Thomas H. Wolff, "Recent work connected with the Kakeya
problem" and "Lecture Notes for CalTech Math 191d-Topics in
Harmonic Analysis" Spring 2000.

---

Sorry to join the discussion this late. I just wanted to add a few points that I remember reading about this problem.

Firstly, I think that the results by Schaer and Wetzel rely on 'shaving' sections off an area already proven to contain the arbitrary worm. This has led to a succession of tiny improvements but mathematical 'intuition' suggests that this won't lead to an optimal solution. I also remember a result that the optimal solution must be convex and contain sharp 'corners'. I think its been shown that an optimal solution must be simply connected?

I think the result that if we restrict ourselves to polygonal worms we can find a covering set of zero measure is built on the same idea as 'cantor sets'. If you recall a cantor set (formed by iteratively removing the central third from a unit line segment) has the property that given any 0 < = x < = 1 you can find two points in the cantor set which are a distance x apart. If you then form a 'cantor tartan' by setting a grid whose horizontal and vertical coordinates are the points in the cantor set, it is easy to see that any quadrilateral worm could be covered by this tartan. Since the cantor set has measure zero, the tartan has measure zero.

I'm not sure how the generalization works but I'd be interested in finding out.

As far as Dan's comment about being unable to tile the plane with uncountably many ellipses goes, I'm not sure that's true. If you consider the set of all circles centred at the origin. They form an uncountable set (they are equinumerous with the real numbers), and they don't intersect. The problem, of course, is that their union forms the entire plane. I suspect there is some mileage to be had by taking unions of sets of curves, but we will always need to place some restrictions on the worm.

I'd love to see an optimal solution. Although I take to heart Michael Dore's comment about the area possibly tending to zero. While its been shown that this doesn't happen, an optimal solution might be very complicated (or fractal) in nature and might not even exist. As a caveat, the problem of finding the shape of minimum area in which a unit line can rotate has no solution, although given epsilon > 0 you can find a solution with area less than epsilon.


p.s. I don't remember where I read all of this but it may have been in Ian Stewart's Game Set and Math - a book which I think I have lost.

Dear Harry,

Do the sets in which one can rotate a unit line actually look reasonable? Do they have any definite "shape" common to all of them, or are they the sort of weird exotic sets that come up in the worm problem? I would have guessed a sort of triangle with concave curved sides and a similar triangle punched out of the middle would work, but are the solutions for given epsilon of this form?

David Loeffler

Dear David,

The answer to your question is yes, the sets in which one can rotate the unit line do have common features. First some background.

The shape you describe, a triangle-style shape with three concave sides (you can't cut a hole out of the middle though), is indeed the first "good" solution you come up with for this problem. The actual nature of the concave curve and the area of the shape can be found using the calculus of variations. It is a deltoid , the curve traced by a point on the circumference of circle of diameter 1 as it rolls around the inside of a circle of diameter 1½. It has area ½pi.

For years after this problem was posed in 1917 mathematicians believed the deltoid was the shape of minimum area in which the unit line could be rotated. It turned out not to be true. Think about why the deltoid works allows you to rotate the line. You can 'push' the end of the line into a corner, rotate the line, and then push the other end of the line into another corner. We are doing a geometric three-point turn.

What happens if we increase the number of corners on our shape? If we turn our shape into a five pointed star we can rotate the line by pushing it into and out of opposite corners. Our rotation becomes a five-point turn. Obviously the optimal five cornered shape will have sides curved in a similar way to the deltoid. Such a shape has area less than ½pi. We can similarly form a 7 pointed star, a 9 pointed star and so on. In each case we rotate our line by pushing it into the (by now very thin) opposite corner, rotating it very slightly, and pushing it into the corner adjacent to the original corner.

The area of the optimal n-pointed star tends to zero as n tends to infinity. If we want an area less than epsilon we simply choose suitably large n.

I am told that the original proof that there was no solution to this problem (called the Kakeya needle problem) was due to Besicovitch in 1927, but I don't think he used this method, and I think the sets he defined for his rotations were very exotic. I might try and seek out his method.

Hope this is interesting.

Harry