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

我现在正在规划一个花园，因此，假设我有 6 个西红柿想要种植在一个尺寸l为w. 我所在地区的西红柿受到枯萎病的影响，因此最大限度地提高番茄植株之间的距离对于最大限度地提高我的总产量非常重要。

我一直在想明显的解决方案是这样的：

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

T代表番茄的位置。然后我认为该解决方案可能与 Steiner 树有关，正如singingbanana 的这段视频中所展示的那样：https ://youtu.be/dAyDi1aa40E

该解决方案可能如下所示：

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

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

标签： algorithmcombinatoricsminimax

这个问题被称为“圆包装”，它的最佳算法是一个开放问题。即使是矩形是正方形的最佳算法仍然是开放的。（尽管事实上我们已经证明了将 1-30 个圆包装在一个正方形中的最佳解决方案。但不是 31 个。）

大量圆形和大面积的最佳总体布置是像蜂窝一样的六角形包装。在您的图表中，放下顶部中间的圆圈，并提高底部的角落圆圈。您会发现，对于许多矩形，您现在可以拟合更大的圆圈。

对于 6 个圆圈的特殊情况，我会简单地提供一个不同包装的列表来尝试，尝试每个包装，看看它可以包装多大。事实上，我建议只尝试两个。第一个是我上面描述的六边形包装。第二个是拍摄图像并将底角向左滑动，顶部向右滑动。