ボロノイ分割からk最近傍の集合を計算するのは比較的簡単です。逆の問題はどうですか？私はすでにk最近傍のセット（3D）を持っており、ボロノイセルの体積と中心を計算したいと思います。直感的には、それを行うO（n）アルゴリズムがあるはずですよね？
誰かがこのようなものがどこかに実装されているのを見たことがありますか？
前もって感謝します
PS：ボロノイセルにはk個を超えるエッジがないと思います（ポイントの位置に関するこの事前知識は、次元に関係なく、O（n）でダイアグラムを計算することを可能にするものです）。
PPS：さらに、特定の点について、ボロノイセルの頂点がkNNのセットに属していると仮定します（以下のコメントを参照）。
VD は次のようにビルドできます。点 P とその k 個の最近傍点の 1 つ Q は、P と Q の両方から等距離の半平面 H(P,Q) と、境界 H を持ち P を含む半空間 H+(P,Q) を定義します。 P のセルは、P の k 個の最近傍にあるすべての Q の H+(P,Q) の交点です。この交点の構築は、頂点列挙問題と非常に密接に関連しています: http://en.wikipedia.org/wiki/ Vertex_enumeration_problem
正しい VD が構築されていることを確認するには、十分な数のネイバーが必要ですが、あなたの仮定がそれを保証するかどうかはわかりません。唯一確かなことは、点 P の実ボロノイ セルが、上記のアルゴリズムが構築するセルに含まれていることです。
直感的なアルゴリズムがあるはずですが、実際にはないと思います。私には正式な証明はありませんが（そしてそれをそれほど速く作成することはできませんでした）、次の議論を検討してください。
点Pのk最近傍点KがすべてPの片側にある場合、つまりK内のすべての点が平面の片側にあるようなPを通る平面がある場合を考えてみます。その場合、Pのボロノイセルの境界は、Kの点からは計算できません。この引数は、任意のkに当てはまり、アルゴリズムが上の任意の点の存在を検出する方法がわかりません。最近傍分析によるPの反対側。したがって、ボロノイ図にはk最近傍統計よりも多くの情報が含まれているため、ボロノイからkNNへの変換は不可逆的な減少であると私は主張します。
一方、Hugo Ledouxは、Voronoizationのlogn平均ケースアルゴリズムを開発しました。その解決策を検討してください。
編集：私の議論はおそらくまだ複雑すぎます。kNNについての簡単な考え：相互にkNNであるk点のクラスターを考えてみましょう。これらの点のkNNサブグラフは他のすべての点から切り離されているため、ボロノイ図を作成することはできません。または、言い換えると、ボロノイ図には任意のkのk最近傍が含まれているため、有限のkから再構築することはできません。