良い提案はロイドのアルゴリズムです。しかし、あなたが求めている「隣人を保護する」特性は明確ではありません。
ただし、求めているのが次の場合：
Vが[0,1]^2の点で構成され、Eがセグメントであり、2つのセグメントの内部が交差しない（つまり、平面グラフがある）グラフ（V、E）が与えられた場合、点は 可能な限り均等に移動します。平面特性の維持
その後、ロイドのアルゴリズムが実行します。
余談ですが、一般化は、どの空間ポイントが存在するかではなく、ポイントにどの密度を要求するかという観点からです（たとえば、R ^ nでガウス測度が必要な場合があります）。
これが可能な戦略のスケッチです。
ポイントの元のセット P に、正方形の境界 (少なくとも正方形の頂点) からいくつかのポイントを追加します。点は境界から均等にサンプリングする必要があり、元々 n 個の点がある場合、境界から少なくとも √n 個の追加点がサンプリングされている必要があります。この拡張セットを Q と呼びます。
次に、Q のDelaunay Triangulationを実行します。次のステップで、この三角形分割からのエッジを使用します。
次に、最小二乗最小化を実行して、エッジ長の二乗和を最小化する P 内の点の位置を見つけます (QP 内の点を固定したままにします)。
この最小化問題は行列式を解くことで解決できるため、これは「直接解」です。
最小二乗問題の解は、エッジの長さを等しくする傾向があります。そのため、小さなエッジは大きくなり、大きなエッジは小さくなります。これにより、トポロジーを維持しながらポイントをより均一に分散させる効果があります。
これは、高次元に簡単に一般化できます。