各点の各座標がp/qの形式の有理数であり、pとqの値が制限されている場合、平面内のn点の凸包をO（n）時間で計算できることを示します。
注：これは宿題の問題です。どういうわけかすべてのポイントのスキャンを回避することで、JarvisMarchを使用することを考えることができます。たぶんこれは、次の点がどこにあるかを確認するために（合理的な条件を使用して）固定された方向に光線を投げることによって行うことができます。
2296 次
1 に答える
6
時間計算量がであるため、JarvisMarchは使用しないでくださいO(nh)。最悪の場合、はとh同じくらい大きくなる可能性がありますn。hこれが船体のポイント数であることに注意してください。
代わりに、たとえば、時間計算量がであるグラハムスキャンO(nlogn)を使用する必要があります。グラハムスキャンアルゴリズムでは、時間計算量はすべてのポイントをソートすることによって支配されます。比較ベースのソートアルゴリズムの時間計算量は。であることに注意してくださいO(nlogn)。
宿題の問題では、ポイントの座標がすべて制限されているという仮定があるため、比較ベースの並べ替えアルゴリズムの代わりに基数並べ替えを使用して、の上限を超えることができます。O(nlogn)ソートされる入力が制限されている場合、基数ソートを使用できることに注意してください。これは、の複雑さを持っていますO(n)。
さまざまな凸包アルゴリズムの比較については、ここを参照してください。
于 2013-02-06T18:48:53.107 に答える