凸包の最適化の検索

Question

私は大きな行列、または2D配列、浮動小数点のMを持っています。今、私の行列は10,000行と31の列を持っています。この行列の各行はベクトルを表します。私は行のセットのconvex hullを計算するために探しています。

この行列はかなり大きいので、私は高速なアプローチを探しています。私の現在のアプローチuses this packageは、O（n²）と同じくらい遅くてもよい。ここで、nはベクトルの数である。私の目標は、このアルゴリズムをさらに大きな行列にスケールすることです。

O（n²）速度よりも速いアプローチがありますか？

私はPythonを使うのが好きですが、私はコードを探していません。私は自分でコード化できる一般的なアルゴリズムを探しています。固定寸法dについて

Answer 1

、Chazelleは[1] scipy.spatialパッケージがあってもよいQHullを使用nポイントの数であり、[d/2]が2で整数除算を表し、最悪の場合、でO(n^[d/2])を必要とする1993年の最適なアルゴリズムを与えました2Dと3Dの点ではO(n^2)のように遅いです。 O(n^2)バウンドは任意の次元で保持されません。

任意の次元で凸包を計算する最も実用的なアルゴリズムは、QHullと同様にランダム化インクリメンタル構造を実装しています。凸包を高次元で計算することは、一般的に難しい問題です。このFAQ [2]をチェックしてください。

Answer 2

凸包の複雑さは、並べ替えアルゴリズムの種類を減らすことができるため、一般的な場合（任意の次元数）はO(n · log n)と低く制限されています。

しかし、平面凸包と呼ばれる特別なケースでは、2Dでウォーキングしています。したがって、O(n · log h)への境界を改善するChan's algorithmを使用できます。nが合計ポイント数で、hが凸包内のポイント数です（この種のソリューションは、明らかな理由から「機密出力アルゴリズム」として知られています）。

最後に、あなたのアルゴリズムとmany other alternativesは、最悪の場合にはO(n^2)まで成長しますが、平均複雑度はO(n · log n)です。したがって、最悪の場合が非常に少ない傾向があるので、それは二次的な複雑さを有すると述べることは間違いである。

Answer 3

私はOuellet Convex HullよりもC＃でO（n log h）のアルゴリズムをプログラムしました。すべてのコードはリンクなどで提供されています。

今日、私はあなたが1つの時点でそれを供給し、1点あたりO（ログh）にとどまることを可能にする「オンライン」バージョンを完成させました。 Chanより一般的な使用法では少なくとも2倍高速です。

この記事では、「オンライン」の部分については言及していません（私は明日何かを書くつもりです）。しかし、このコードはプロジェクト：OuelletConvexHullAvl2OnlineのGitHubからアクセス可能です。

使用法：

OuelletConvexHullAvl2Online.ConvexHullOnline convexHullOnline = new OuelletConvexHullAvl2Online.ConvexHullOnline(); 
        foreach (Point pt in points) 
        { 
         convexHullOnline.DynamicallyAddAnotherPointToConvexHullIfAppropriate(pt); 
        } 

        return convexHullOnline.GetResultsAsArrayOfPoint();