交差していない楕円の近傍の三角形

Question

私は、任意に配置された交差しない楕円の集合に対して最も近い三角形を見つける問題に取り組んでいます。新しいユーザーとして、画像タグを含めることはできませんが、ページの下部にURLを含めました。視覚援助で自分自身を説明することができると思っています。写真は、3つの最も近い楕円を互いに接続するアポロニアスの円で私が何を意味するかを示しています。

これまで私は、楕円間の最小距離を使って、Delaunay Triangulationを、IncrementalとSweeplineの方法で修正し、3つの楕円の構成などの間に形成される三角形の円に関わるさまざまな手法を使用して試しました。

私は解決策を見つけ出しましたが、楕円のすべての三角形を徹底的に検索し、他の楕円と比較し、時間の複雑さはn(n-1)(n-2)/3!です。さらに、各計算は代数的にではなく繰り返し実行されます。

誰でも、これを代数的に行うことができますか、それより低いところでn^2時間の複雑さを考えることができますか？

技術の提案でさえ、試してみるのに適しています。なぜなら、今は私が3週間近く働いていて本当にまともな答えに近づいていないからです。

Image http://img859.imageshack.us/img859/727/nearesttrio.png

Answer 1

あなたが楕円のためのボロノイ図を計算する場合は、サークルの中心点は、図の交差点に配置されることになります。

http://ima.umn.edu/nuggets/voronoi.html

Answer 2

あなたはそれらのバウンディングボックスに基づいてR-treeにあなたの楕円を詰めることができました。 Rツリーは、空間オブジェクトのバイナリツリーのようなデータ構造であり、トラバーサルを介して効率的な最近傍クエスチョンとk番目に近い近接クエリーをサポートします。

多くの省略記号を含む大量のデータセットの場合、Rツリーを使用すると、距離テストの数が大幅に削減され、クエリの近隣にあるツリーのサブセットのみをスキャンする必要があります。

これが役に立ちます。