各エッジに関連付けられた距離を持つ完全な無向グラフGがあるとします。長さlのエッジ（u、v）の意味は、「点uとvをl以外に近づけることはできない」ということです。私の目標は、これらの距離の制約に違反しないように、またポイントの凸包の総面積が最小になるように、このグラフのノードを平面に配置することです。例として、チップに入れたい電気部品がたくさんあり、それぞれがある程度の電気的干渉を生成するとします。コンポーネントを近づけすぎると、コンポーネントが互いに干渉し始め、システム全体が役に立たなくなります。各ポイントが他のポイントからの最小距離を考えると、コンポーネントをチップに配置する最もスペース効率の良い方法は何ですか？
どうやってこれを考え始めるのかさえ分かりません。また、問題がより高次元の場合（超平面に点を詰め込む）にどのように一般化されるかもわかりません。この問題に取り組む良い方法を知っている人はいますか？
私には最適な解決策がありますが、あなたはそれを気に入らないでしょう:)。
ノードにx0、x 1、...、xnというラベルを付けましょう。B = max i、j <n（dist（x i、x j））とします。ここで、dist（x i、x j ）はxiとxjの間の最小距離です。各iについて、ノードx iを位置（0、i * B）に配置します。これで、各ノードは他のすべてのノードから少なくともB離れており、凸包の面積は0になります。
ここでの本当のポイントは、凸包の面積を最小化するだけで無意味な解決策が得られるということです。おそらくより良い尺度は凸包の直径でしょう。
最適なアルゴリズムを見つけるのは難しいと思います。それがNP困難な問題であることが判明したとしても、私は驚かないでしょう。ただし、適切なソリューションを生成する実用的なアルゴリズムに興味がある場合は、力ベースのグラフ描画アルゴリズムを確認することをお勧めします。
これが一般的な考え方です（より高度な数学が表示されます）。これは、任意の数の次元に一般化されます。
各ノードレイアウトに値（最小化する値）を割り当てる関数fを作成します。あなたの場合、関数は与えられたレイアウトの凸包の面積+満たされていない各制約に対する大きなペナルティを計算することができます。gまたは、前者を合理的に近似するより単純な関数である可能性があります。つまり、g小さくなるたびfに小さくしたい、またはその逆です。（ノードの座標に関して）偏導関数を計算する必要があるため、比較的単純な関数を選択することをお勧めします。
ここで、100個のノードがあり、それらを3Dでレイアウトしたいとします。つまり、300個の未知の数があります（100ノード×各ノードの3座標）。関数fはR300からRまでの関数であり、理想的にはそれがグローバルな最小値を見つけたいと考えています。より現実的には、十分に深い極小値で十分です。
このような最小値を見つけるためのよく知られた数値アルゴリズムがあります。たとえば、共役勾配法、BFGS法です。良いことは、それらを詳細に理解する必要はないということです。これらのアルゴリズムは多くの言語で実装されています。あなたがしなければならないのは、計算の方法と、アルゴリズムによって要求されたもの、および初期レイアウトを提供するf(x)ことです。f'(x)xx₀
これは2Dビンパッキング問題（NP困難）であり、追加の制約があります。シミュレーテッドアニーリングは、回路/チップの設計に非常に適していると聞きました。
DroolsPlannerの大きなビンパッキング問題の実際のテストデータを実際に探しています。