CODEWITHSUNDEEP
algorithmcombinatoricsminimax
ijustlovemath
ijustlovemath

Reputation: 938

How do I place k points in an area A, such that the distance between any two points is maximized?

I'm planning a garden right now, and as such, let's say I have 6 tomatoes I want to plant in a garden with dimensions l by w. Tomatoes in my area are affected by blight, so maximizing distance between tomato plants is very important for maximizing my overall yield.

I've been thinking the obvious solution is something like this:

T---------T--------T
.                  .
.                  .
.                  .
.                  .
.                  .
T---------T--------T

with T representing the location of a tomato. Then I thought the solution might be related to Steiner trees, as shown quite well in this video from singingbanana: https://youtu.be/dAyDi1aa40E

That solution might look like this:

T------------------T
.                  .
.                  .
.      T      T    .
.                  .
.                  .
T------------------T

But perhaps that solution is also minimizing distance. I'm not really sure, but I'm guessing this is a problem with a known solution that I could employ for this use case!

Upvotes: 1

Views: 137

Answers (1)

btilly
btilly

Reputation: 46408

This problem is called "circle packing" and a best algorithm for it is an open problem. Even a best algorithm for the case the rectangle is a square is still open. (Though in fact we have proved optimal solutions for packing 1-30 circles in a square. But not for 31.)

See https://math.stackexchange.com/questions/701/how-many-circles-of-a-given-radius-can-be-packed-into-a-given-rectangular-box for some discussion of this.

The optimal general arrangement for lots of circles and a large area is a hexagonal packing like in a honeycomb. In your diagram drop the top middle circle, and raise the bottom corner circles. You will find that, for many rectangles, you can now fit larger circles.

For the special case of 6 circles, I would simply provide a list of different packings to try, try each and see how big it could be packed that way. In fact I would suggest only trying two. The first is the hexagonal packing that I described above. The second is to take your image and slide the bottom corners towards the left and the top ones towards the right.

Upvotes: 2

Related Questions