Positioning squares on a circle with minimum diameter

I would calculate an upper bound of the minimum radius, by working with circles enclosing the squares instead of with the squares themselves.

My calculation results in:

Rmin <= X / (sqrt(2) * sin (180/N) )

Where: X is the square side length, and N is the required number of squares.

I assume that the circles are positioned such that their centers fall on the big circle's circumference.

-- EDIT --

Using the idea of Dave in the comment below, we can also calculate a nice lower bound, by considering the circles to be inside the squares (thus having radius X/2). This bound is:

Rmin >= X / (2 * sin (180/N) )

There may be a mathematically clever way to do this, but I wouldn't know. I think it's complicated a bit by the fact that the geometry is different for every different number of squares; for 4 it's a rhombus, for 5 it's a pentagon and so on.

What I'd do is place those squares on a 1 unit circle (much too small, I know, bear with me) distributed equally on it. That's easy enough, just subtend (divide) your 360 degrees by the number of squares. Then just test all your squares for overlap against their neighbors; if they overlap, increase the radius.

You can make this procedure less stupid than it sounds by using an intelligent algorithm to approach the right size. I'm thinking of something like Newton's algorithm: Given two successive guesses, of which one is too small and one is too big, your next guess needs to be the average of those two.

You can iterate down to any precision you like. Stop whenever the distance between guesses is smaller than some arbitrary small margin of error.

EDIT I have a better solution:

I was thinking about what to tell you if you asked "how will I know if squares overlap?" This gave me an idea on how to calculate the circle size exactly, in one step:

Place your squares on a much-too-small circle. You know how: Calculate the points on the circle where your 360/n angles intersect it, and put the center of the square there. Actually, you don't need to place squares yet, the next steps only require midpoints.

To calculate the minimum distance of a square to its neighbor: Calculate the difference in X and the difference in Y of the midpoints, and take the minimum of those. The X's and Y's are actually just cosines and sines on the circle.

You'll want the minimum of any square against its neighbor (clockwise, say). So you need to work your way around the circle to find the very smallest one.

The minimum (X or Y) distance between the squares needs to become 1.0 . So just take the reciprocal of the minimum distance and multiply the circle's size by that. Presto, your circle is the right size.

EDIT

Without losing generality, I think it's possible to nail my solution down a bit so it's close to coding. Here's a refinement:

• Assume the squares have size 1, i.e. each side has a length of 1 unit. In the end, your boxes will surely be larger than 1 pixel but it's just a matter of scaling.

• Get rid of the corner cases:

  if (n < 2) throw new IllegalArgumentException();
  if (n == 2) return 0.5; // 2 squares will fit exactly on a circle of radius 0.5
  

• Start with a circle size r of 0.5, which will surely be too small for any number of squares > 2.

  r = 0.5;
  dmin = 1.0; // start assuming minimum distance is fine
  a = 2 * PI / n;
  for (p1 = 0.0; p1 <= PI; p1+=a) { // starting with angle 0, try all points till halfway around
     // (yeah, we're starting east, not north. doesn't matter)
     p2 = p1 + a; // next point on the circle 
     dx = abs(r * cos(p2) - r * cos(p1))
     dy = abs(r * sin(p2) - r * sin(p1))
     dmin = min(dmin, dx, dy)
  }
  
  r = r / dmin;
  

---

EDIT

I turned this into real Java code and got something quite similar to this to run. Code and results here: http://ideone.com/r9aiu

I created graphical output using GnuPlot. I was able to create simple diagrams of boxes arranged in a circle by cut-and-pasting the point sets from the output into a data file and then running

plot '5.dat' with boxxyerrorbars

The .5's in the file serve to size the boxes... lazy but working solution. The .5 is applied to both sides of the center, so the boxes end up being exactly 1.0 in size.

Alas, my algorithm doesn't work. It makes the radii far too large, thus placing the boxes much further apart than necessary. Even scaling down by a factor of 2 (could have been a mistake to use 0.5 in some places) didn't help.

Sorry, I give up. Maybe my approach can be salvaged, but it doesn't work the way I had though it would. :(

---

EDIT

I hate giving up. I was about to leave my PC when I thought of a way to salvage my algorithm:

The algorithm was adjusting the smaller of the X or Y distances to be at least 1. It's easy to demonstrate that's just plain silly. When you have a lot of boxes then at the eastern and western edges of the circle you have boxes stacked almost directly on top of each other, with their X's very close to one another but they are saved from touching by having just enough Y distance between them.

So... to make this work, you must scale the maximum of dx and dy to be (for all cases) at least the radius (or was it double the radius?).

Corrected code is here: http://ideone.com/EQ03g http://ideone.com/VRyyo

Tested again in GnuPlot, it produces beautiful little circles of boxes where sometimes just 1 or 2 boxes are exactly touching. Problem solved! :)

(These images are wider than they are tall because GnuPlot didn't know I wanted proportional layout. Just imagine the whole works squeezed into a square shape :) )