(ソース: hiveworkshop.com )
上の図では、20 個の任意のポイントを 5 つのクラスターに分割しています。右側には、最大クラスター サイズを定義する円があります。右上はクラスターあたりの最大ポイントです。ポイント k の任意のセットを取り、それらを最大半径 r の最大サイズ n のクラスターに分割できるようにしたいと考えています。可能な限り完全なクラスターを取得するアルゴリズムが必要です(上記の例では、できるだけ多くの 4 つのクラスター)。任意のポイントは 1 つのクラスターにのみ属することができ、クラスターが重複することはありません。
アルゴリズムが既存のセットにポイントを追加/削除し、クラスターを更新できる場合も役立ちます。
これを達成する方法について、私は完全に迷っています。これまでの私の最善のアイデアは、ポイントのセットの中心を計算し、それらの中心をバイナリ空間分割に使用することでしたが、そのアプローチを使用して期待できる最善の方法は、クラスターが均等に分散されることです。
どんな助けでも大歓迎です:)。
edit
領域が形成する形状が他の領域が形成する形状と交差せず、その領域が他の領域の内側に位置しない (例えば、円の中の円) ように重ならないでください。上の図では、各領域に形状があります。これらの形状はいずれも交差せず、別の領域内に領域はありません。