tem*_*def 17 language-agnostic algorithm packing
假设我有一个完整的,无向图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.
这里真正的要点是,单独最小化凸包的面积将为您提供一个无意义的解决方案.一个可能更好的措施是凸包的直径.