如何在区域A中放置k个点，以使任意两个点之间的距离最大化？

Question

我正在计划一个花园，因此，假设我要在尺寸为l乘w的花园中种植6个西红柿。我所在地区的番茄受到疫病的影响，因此，最大化番茄植株之间的距离对于最大限度地提高整体产量非常重要。

我一直在想显而易见的解决方案是这样的：

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

T代表番茄的位置。然后，我认为解决方案可能与Steiner树相关，如在唱歌香蕉的视频中很好地展示了这一点：https://youtu.be/dAyDi1aa40E

该解决方案可能看起来像这样：

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

但是也许该解决方案还可以使距离最小化。我不太确定，但我猜这是我可以在此用例中使用的已知解决方案的问题！

Answer 1

此问题称为“圆堆积”，并且针对它的最佳算法是一个开放问题。对于矩形为正方形的情况，即使是最佳算法也仍然开放。 （尽管实际上我们已经证明了将一个正方形包装1-30个圆的最佳解决方案。但是对于31个圆来说不是。）

请参见https://math.stackexchange.com/questions/701/how-many-circles-of-a-given-radius-can-be-packed-into-a-given-rectangular-box对此进行一些讨论。

对于许多圆形和大面积的最佳总体布置是像蜂窝状的六边形填料。在图表中，放下顶部中间的圆圈，然后放下底部的角圆圈。您会发现，对于许多矩形，现在可以容纳更大的圆形。

对于6个圆的特殊情况，我只提供一个不同包装的清单，尝试一下，尝试每个包装，然后看看用这种方式包装的大小。实际上，我建议只尝试两个。第一个是我上面描述的六角形填料。第二种是拍摄图像，并将底角向左滑动，将顶角向右滑动。