近似アルゴリズムを探している場合は、k-meansアルゴリズムまたは階層的クラスター、特にモンスター曲線または空間充填曲線を探すことをお勧めします。まず、グラフの最小スパニングツリーを計算してから、最も長くて最も高価なエッジを削除します。次に、ツリーは多くの小さなツリーを作成し、k-meansを使用してポイントのグループ（クラスター）を計算できます。
「シングルリンクkクラスタリングアルゴリズムは...正確にはクラスカルのアルゴリズムです...MSTを見つけてk-1の最も高価なエッジを削除するのと同じです。」たとえば、ここを参照してください： https://stats.stackexchange.com/質問/1475/ visualization-software-for-clustering 。
モンスターカーブの良い例はヒルベルトカーブです。この曲線の基本的な形はU字型であり、その多くを一緒にコピーして回転させることにより、曲線は真核生物の空間を埋めます。驚くべきことに、グレイコードはこのU字型の向きを見つけるのに役立ちます。 Nickの空間インデックス四分木ヒルベルト曲線
この画像では、ヒルベルト曲線を使用して緑色のポリゴンが検出されていることがわかります。
私のphpクラスはここにあります： http://www.phpclasses.org/package/6202-PHP-Generate-points-of-an-Hilbert-curve.html