ボロノイ図の作成にはFortunes algorithmを実装する必要があります。Fortuneアルゴリズム - ビーチラインデータ構造
アルゴリズムの重要な部分は、「ビーチラインデータ構造」と呼ばれるデータ構造です。
これはAVLに似ていますが、データがリーフにのみ格納される方法では異なります（その他の違いはありますが、質問には重要ではありません）。
私はそれを実装する方法がわかりません。明らかにAVLを「そのまま」使用することは、AVLツリーリーフノードが内部ノードになることができ、その逆になることができるので機能しません。
私はまた、ウィキペディアの他の既知のデータ構造を見ようとしましたが、ニーズに合っていません。 リンクリストでこれを行ういくつかの実装を見ましたが、リンクされたリストを検索するとO（n）であり、アルゴリズムが効率的であるためにはO（log n）である必要があるため、
イベント構造体の内部ノード（"ビーチラインツリー"）は、放物線/円弧が隣り合う点の順序付きタプルを格納します。 P 形態を指す放物線はP B（これら二つの放物線の交差）、内部ノードストア順序付けタプル（P 、Pによって形成される放物線の左側に位置する場合b）。
AVLツリーリーフノードをバランシングすると内部ノードになることができ、その逆もあり得るため、明らかにAVLを「そのまま」使用すると機能しません。
AVLツリーにさまざまな種類のオブジェクトを格納することを心配している場合、簡単な方法はタプルとして葉を保存することです。だから、ポイントP jの葉など格納されませんが、代わりにタプル（P J、P J）を格納します。もしP J葉は、イベントツリーから消え（ビーチライン）、およびその親が（P I、P J）あり、単に、（P Jに親を変更するとP J）、そしてもちろんその親もに（P J、P ？）から変更する必要があります（P I、P ？）などと同様に、通常のAVLツリーと同様に、ツリーを歩き、変更および/または再調整が必要な内部ノードを変更します。
アルゴリズムの優れた実装は、SO答え（少なくとも私ではなく！）に簡単に書き込むことはできません。それによって使用されるデータ構造の説明を含むアルゴリズム全体の適切な説明については、Computational geometry: algorithms and applications by Mark de Berg et al.を参照してください。第7章では、ボロノイの図のみを扱っています。