algorithm - 飞机上的密密麻麻点？

Question

假设我有一个完整的无向图 G，每条边都有一个距离。长度为 l 的边 (u, v) 的含义是“点 u 和 v 不能比 l 更靠近彼此”。我的目标是将此图的节点布置在一个平面上，这样就不会违反这些距离约束，并且这些点的凸包具有最小的总面积。例如，假设我有一堆电子元件要放在芯片上，每个元件都会产生一定量的电子干扰。如果我把组件放得太近，它们就会开始相互干扰，使整个系统变得毫无用处。给定每个点与其他点之间的最小距离，将组件放置在芯片上的最节省空间的方法是什么？

我什至不知道如何开始考虑这个问题。我也不知道这个问题如何推广到更高维的情况(将点打包到超平面中)。有谁知道解决这个问题的好方法？

Answer 1

我有一个最佳解决方案，但您不会喜欢它:)。

让我们标记我们的节点 x₀, x₁, ..., x_n。令 B = max_{i,j < n}(dist(x_i, x_j))，其中 dist(x_i, x_j) 是 x_i 和 x_j 之间的最小距离。对于每个 i，将节点 x_i 放在位置 (0, i*B)。现在每个节点与所有其他节点至少相距 B，并且凸包的面积为 0。

这里的真正要点是，单独最小化凸包的面积会给你一个荒谬的解决方案。一个可能更好的度量是凸包的直径。