2D空間内の与えられた点をカバーする最も狭いバンドを見つける方法は？

Question

2D空間でnポイントが与えられた場合、これらのポイントをカバーする最も狭いバンドを見つけたいと思います。言い換えれば、私はすべての点がこれらの2つの線の間に入るように2本の平行な線を見つけたいと思う。効果的なアルゴリズムが終了していますか？

Answer 1

まず、これらの行は、ポイントのconvex hullを形成するポイントを通過する必要があります。凸包は多くの人によって発見される可能性がありますdifferent algorithms。選択はデータによって異なります。

第二に、私たちの平行線の一つは、凸包セグメントを通過します。凸包の他の点で停止するまで、両方の平行線を回転させて、それらの間の距離を減少させることができるからです。

今、私たちは、すべての凸包セグメントを反復処理し、すべてのセグメントに対して、このセグメントを通過するラインを構築し、このラインから最も離れた凸包点を見つける必要があります。これらの距離の最小値（最も遠い点から線まで）が答えになります。このすべての反復は、rotating calipers（MBoのおかげで）を使用して線形時間で行うことができます。