search - 一定サイズまたは三角形の凸包

Question

凸包が三角形であるか、サイズが一定の場合、QuickHull アルゴリズムは Theta(n) で実行されることを知っています。

これはどういう意味ですか？

アルゴリズムは 4 つの極値を使用するため、形状についてはわかりません (三角形に見える場合)。

ありがとう

Answer 1

凸包の頂点の数 letHが定数 ( に依存しないN) の場合、QuickHull はN(より正確にc1.N < T < c2.Nは 2 つの定数c1との場合c2) に比例する時間がかかります。

の場合H=3、ハルは三角形です。アルゴリズムの動作に関係なく、この三角形を返さなければなりません。慎重な実装は、H=2(線分) またはH=1(単一の点) に対しても機能するはずです。