假设我有一个完整的无向图 G，其距离与每条边相关联。长度为 l 的边 (u, v) 的含义是“点 u 和 v 不能比 l 更接近”。我的目标是将这个图的节点放在一个平面上，这样就不会违反这些距离约束，并且点的凸包的总面积最小。举个例子，假设我有一堆电子元件想放在一个芯片上，每个元件都会产生一定量的电子干扰。如果我将组件放在一起太近，它们就会开始相互干扰，从而使整个系统变得毫无用处。给定每个点与其他点之间的最小距离，将组件放置在芯片上的最节省空间的方法是什么？
我什至不知道如何开始考虑这个问题。我也不知道问题如何推广到更高维的情况（将点打包到超平面中）。有谁知道解决这个问题的好方法？
我有一个最佳解决方案，但你不会喜欢它:)。
让我们标记我们的节点 x 0 , x 1 , ..., 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。
这里真正的要点是，仅最小化凸包的面积会给你一个荒谬的解决方案。一个可能更好的测量方法是凸包的直径。
我想很难找到最佳算法。如果它被证明是一个 NP 难题，我不会感到惊讶。但是，如果您对产生体面解决方案的实用算法感兴趣，我建议您查看基于力的图形绘制算法。
这是一般的想法（会出现一些更高的数学）。它可以推广到任意数量的维度。
构造一个函数f，为每个节点布局分配一个值——一个你想要最小化的值。在您的情况下，该函数可以计算给定布局的凸包面积 + 对每个未满足的约束的巨大惩罚。或者它可以是一个更简单的函数，它可以g合理地逼近前一个函数：简而言之，g只要f变小，我们就希望变小，反之亦然。最好选择一个相对简单的函数，因为您需要计算它的偏导数（相对于节点的坐标）。
现在假设您有 100 个节点，并且您想以 3D 形式布置它们。这意味着您有 300 个未知数（100 个节点乘以每个节点的 3 个坐标）。Functionf是从R 300到R的函数，理想情况下我们希望找到它的全局最小值。更现实地说，足够深的局部最小值就足够了。
有众所周知的数值算法可以找到这样的最小值，例如：共轭梯度，BFGS。好消息是，您实际上不必详细了解它们，这些算法是用多种语言实现的。您所要做的就是提供一种计算方法，f(x)并f'(x)为x算法所要求的任何内容，以及一个初始布局x₀。
这是带有额外约束的 2D装箱问题（这是 NP 难题）。我听说模拟退火在电路/芯片设计中表现得非常好。