51

We know that there is no paper-and-scissors solution to Tarski's circle-squaring problem (my six-year-old daughter told me this while eating lunch one day) but what are the closest approximations, if we don't allow overlapping?

More precisely: For N pieces that together will fit inside a circle of unit area and a square of unit area without overlapping, what is the maximum area that can be covered?

N=1 seems obvious: (90.9454%)

A possible winner for N=3: (95%)

It seems likely that with, say, N=10 we could get very close indeed but I've never seen any example, and I doubt that my N=3 example above is even the optimum. (Edit: It's not!) And I've no idea what the solution for N=2 would look like.

This page discusses some curved shapes that can be cut up into squares. There's a nice simple proof here that there's no paper-and-scissors solution for the circle and the square.

Community
  • 1
tim_hutton
  • 964
  • 10
    That's so cool your 6 year old is considering problems like this! – Euler....IS_ALIVE Nov 05 '13 at 23:31
  • 10
    Your daugther is awesome! –  Nov 05 '13 at 23:42
  • 10
    She put it like this "You can't cut up a circle to make a square". I had to look it up but she's quite right. – tim_hutton Nov 05 '13 at 23:49
  • 1
    What a fantastic question! Another (non-equivalent!) way of formulating the problem, incidentally, is 'what's the smallest radius of a circle that can be dissected into N pieces that can be reassembled to cover a unit sqare?' - that version seems to come closer to the usual formulations of packing problems I've seen (e.g. over at mathpuzzle.com ) – Steven Stadnicki Nov 20 '13 at 17:51
  • @Steven: I don't think that's equivalent: both disassembling the disk and covering the square don't allow for holes in these shapes. So it seems related, but if it really is equivalent I don't see how. – MvG Nov 20 '13 at 21:07
  • 1
    I'd love to see some numerical experiments on this: start with a random offset, intersect square and circle to form first tile. Cut away that tile, intersect remainder, and continue until the desired number of tiles have been generated. Then do some numerical optimization to adjust the values of all these offsets simultaneously, thus finding a local minimum. Do the same for a number of random starting offsets and hope to find something that resembles a global optimum. Should give some insight, even in case it does not work. Unsure whether I'll find time to implement this, definitely not soon. – MvG Nov 20 '13 at 21:08
  • 1
    @MvG I agree - you'll note I said 'non-equivalent', not 'equivalent'. :-) I just think it's another interesting interpretation of the core question that might dovetail better with things that have already been studied. – Steven Stadnicki Nov 20 '13 at 21:10

4 Answers4

34

Not really an answer but there are some fantastic dissections on this page, including these two:

Dissecting an octagon into a square with five pieces:

enter image description here

Dissecting a dodecagon into a square with six pieces:

enter image description here

It looks likely that these could be made into pretty good approximations of a square-circle dissection for N=5 and N=6.

Edit: Indeed, with N=6 we can get coverage of 97.18% like this:

Six pieces can cover 97.18% of a circle and a square of equal area
(an inscribed dodecagon would have an area of 95.49%)

Later edit: It turns out that with N=6 we can do much better. 98.80%:

Six pieces can cover 98.6% of a circle and a square of equal area

These solutions were found with a web app I've made:
https://github.com/timhutton/circle-squaring

Please give it a go, and submit the best solutions you find! The leaderboard on the right shows the current best known solutions for N=1 to N=10.

tim_hutton
  • 964
  • 1
    (+1) interesting approach. Any idea how to generalize this using other regular polygons? – achille hui Nov 20 '13 at 13:41
  • @achillehui: This paper points out that the Wallace–Bolyai–Gerwien theorem says that it is possible, and gives a construction. But they end up with a large number of pieces: 9 for an octagon and 15 for a dodecagon. – tim_hutton Nov 20 '13 at 13:50
  • Thanks for the link. What I'm more interested is the number of pieces one need to rearrange the $n$-gon. This should translate to a lower bound of covering ratio of $N$-pieces in this problem. – achille hui Nov 20 '13 at 15:43
  • @achillehui: Good point that we can get a lower bound that way. The numbers in the paper are for rearrangement by translation only but still give a lower bound, e.g. 95.49% for N=15. – tim_hutton Nov 20 '13 at 20:38
22

Well, here's a specific infinite family of scissors congruences between large portions of the circle and large portions of the square. I make no claim that these are close to optimal.

We begin by inscribing a regular $n$-gon in the circle. We then cut the $n$-gon into $2n$ triangles, and rearrange these as follows:

enter image description here

The $2n$ triangles always fit into a rectangle whose width is half the circumference of the circle (namely $\sqrt{\pi}$), and whose height is the radius of the circle (namely $1/\sqrt{\pi}$). This rectangle can be cut into three pieces that can be rearranged to form a unit square:

enter image description here

Composing these two scissors congruences gives the desired infinite family. Note that we may need to cut each of the $2n$ triangles into as many as $3$ pieces to compose with the second scissors congruence, so this uses at most $6n$ pieces. (Actually, it uses slightly fewer pieces than this, since the triangles on the left part of the rectangle won't need to be cut.)

The portion of the area used is the area of the $n$-gon: $$ \text{Area} \;=\; \frac{n}{\pi} \cos(\pi/n) \sin(\pi/n) \;\approx\; 1 - \frac{\pi^2}{2n^2} $$ Thus the leftover area can be made to decrease quadratically with the number of pieces.

Jim Belk
  • 49,278
  • 1
    This is a nice general technique for finding a lower bound, but it doesn't give an optimal answer. For example, the n-gon should be cut into n triangles, and then one of those triangles should be bisected, allowing the construction of your rectangle with only n-1 pieces instead of 2n. Even then, it doesn't approach optimality. – Ed Pegg Dec 04 '13 at 05:44
5

Ok not my greatest piece of work ever, but here's a suggestion in 2 parts: enter image description here

Robert Frost
  • 65
3

I believe I have found the optimal method for n=6 and n≥10.

Above you state that an inscribed dodecagon yields coverage of 95.49%, which you demonstrate is not the best answer. You were on the right track, but a better approach is to overlay the circle with a dodecagon of equal area, and then dissect that into its classic 6 pieces. These can be rearranged into a square of equal area with ~99.108% coverage, which unless the linked computer program rounds incorrectly, is better than the best answer achieved by that program so far. Pictures and discussion of best answers for other numbers of pieces can be found here: https://i.stack.imgur.com/7PKBt.jpg.

What I've found suggests that possibly the best you can get with n=10 is 99.347%, which as you predicted, is very close indeed.

Zachary Krueger
  • 31