OSDev.org

I, as so many times before, have a problem which is starting to give me brain cancer or something. At least my head hurts.

Anyway, the problem is this.

I have a rectangular 2d surface and this area need to be covered circular areas, the centre of which cannot lie outside the borders of the rectangle. The trick is then to use the least amounts of circles.

I know this all sounds very odd because I don't really know how to explain the problem, so I've made an example.

For my purpose the rectangle is 479*989 and the circles all have a radius of 21.6.
In this example 432 circles are used.
http://myhideout.eu/temp/cnd.svg

The above example don't quite follow the rules though, as several of the circles have a centre lying outside the bounds of the rectangle.

I should think that this is not a new problem and that probably there's some fancy formula or something.
In any case, if you're able to help, I'll be very grateful


Best regards.

Its to be done with floors/ceils. Since you know how the pattern must be, you can calculate how much space each circle can fill up, then divide that over the size of the image, no?

Hi,
Idea would be create an equation or function that describes the situation and find out the maxima and minima using differential calculus.But I myself am not quite clear with the rules from the example you gave.Hope it gives you some direction.

Hopefully this gives you a start : http://en.wikipedia.org/wiki/Maxima_and_minima

--Thomas

The way you allow those circles to overlap, it looks like a hexagonal tesselation problem. You ought to be able to express the hexagon's dimensions in terms of the circle's radius. Not too difficult from there.