1

Jarvis: このアルゴリズムは、h 個の極値ポイントを持つ n 個の入力ポイントに対して、最悪の場合に O(nh) 時間を必要とします。

Graham: 最悪のシナリオでは O(nlogn) です。

2 つのアルゴリズムを使用する CGAL のリファレンスを入手します。

つまり、h が logn より小さい場合、Jarvis はデータセット (2 次元としましょう) に対して高速になる可能性があります。しかし、私は実際にそれを見たいと思っていますが、この目的のためのデータセットを見つけることができません. 誰か知っていますか？

グーグルはこのリンクを生成します。これは、私が上記で主張していることを実際にサポートしています。

4

2 に答える 2

4

少し前に同様のことをしたので、受け入れられた回答があっても、数字だけのために回答を投稿しています...

船体に 10^6 ポイントと 3 ポイントを持つ CGAL の実装を使用すると、Graham は最大 150 ミリ秒、Jarvis は最大 87 ミリ秒かかります。セットアップを参照してください (青い四角は他のすべてのポイントです)。 ここに画像の説明を入力

船体の3つのポイント：

points| Jarvis | Graham
10^7  | 850ms  | 1820ms
10^6  | 87ms   | 150ms
10^5  | 10ms   | 15ms

船体の 5 つのポイント:

points| Jarvis  | Graham
10^7  | 1500ms  | 1820ms
10^6  | 139ms   | 150ms

船体の6つのポイント：

points| Jarvis  | Graham
10^7  | 2560ms  | 1820ms
10^6  | 170ms   | 150ms

しかし、これらのいくつかの特殊なケースを除けば、Graham は Jarvis よりもはるかに高速です。

于 2014-08-03T23:51:23.157 に答える
2

大きなトレイングルとその中にたくさんのポイントがあると仮定しましょう。船体上の点の数 (つまり、h) は 3 です。内部の点の数が非常に大きい場合、h = 3 は log n よりも少なくなります。ここではJarvisの方がはるかに高速です。

于 2014-08-03T23:24:01.397 に答える