私は、任意に配置された交差しない楕円のセットに対して最も近いトリオの隣人を見つけるという問題に取り組んでいます。新規ユーザーなので、画像タグを含めることは許可されていませんが、ページの下部に URL を含めました。これは、視覚補助を使用した方が自分自身を説明できるといつも思っているからです。この図は、最も近い 3 つの楕円を互いに接続するアポロニウスの円で私が何を意味するかを示しています。
これまでのところ、楕円間の最小距離を使用して、増分法とスイープライン法を介して Delaunay Triangulation を修正し、3 つの楕円構成ごとに形成される三角形の円を含むさまざまな手法を使用し、境界ボックスを使用して隣接点を推定しようとしました。これを実際に効率的に機能させる方法のアイデアが完全に尽きました
私は解決策を考え出しましたが、それは楕円のすべてのトリオを他のすべての楕円と徹底的に検索して比較することを含み、時間の複雑さはn(n-1)(n-2)/3!です。その上、各計算は代数的ではなく反復的に行われます。
代数的に行うことができ、n^2時間の複雑さよりも低い方法でこれを行う方法について、誰かがアイデアを持っているでしょうか?
テクニックの提案でさえ、試してみるのに適しています.3週間近く取り組んできたので、まともな答えにはほど遠いです.
