探リモートポイント2D

Question

をセットにしたポイントは無限大、倍精度)は2Dです。

さらに凸包がこのセットには、どのように見つめ、 内部 の凸比較的から遠く離れたすべてのポイントを入力す。

下図では、黒点のオリジナルセットの寛地域のスペースを取り上げるすべてのポイントした場合"成長"として半径R

オレンジ色のポイントは例えたいと思います。すいかがうものがあれば、どこからでも比較的離れていて、黒ます。

探検索http://en.wiki.mcneel.com/content/upload/images/point_far_search.png

---

更新:使べてのアルゴリズムによる大きな三角形のように大きなアプローチのための本:べての解決http://en.wiki.mcneel.com/content/upload/images/DelaunaySolutionToInternalFurthestPoints.png

Answer 1

これは KDツリーを用いて解くことができる問題の良い例であります> ...数値レシピ第三加えて、いくつかの良いノートがあります。

あなたが比較的孤立している点の位置を見つけようとしている場合は、

...多分最大のクワッド要素の中心は良い候補になります。

複雑さはO（N ^ 2 n個のログ）... KD-ツリーを作成し、クワッドサイズのソートされたリストを作成するためにはO（nはn個のログ）になりますでしょう。ポイントさえ多数のための合理的なようです（もちろん、あなたの要件に応じて）ます。

Answer 2

このナイーブアルゴリズム

1. 一覧を取得ポイントの凸形状です。
2. そのうちの最小距離が他のポイント。
3. ランクのすべてのポイントは、それぞれR値
4. 選択のトップx。

(2)に思いを馳せることとして半径の検索ものを意味だと思いますの算定の距離から各点各点で否を調べられる点にある内径のもポイントのひとつと同じことの距離をます。

の最適化を検索し、分裂することができるスペースにグリッドに割り当て各ポイントをグリッド。そして、自分の検索(2)のチェックと同じスクエア や 周辺の8訳です。場合の最小距離もポイントのひとつに 同 スクエア、返さなければならないかを指します。だから8までの距離は、"外"の9きに近いトレージエンジンはインデックスは次の概要電所外の方は9切に近いよりも、この9.洗/繰り返す。