凸包

凸包 †

このページは競技プログラミングに興味のある方向けに凸包を簡単に説明するページです

凸包って？ †

平面上に与えられた点をすべて含む多角形で最も点の数が少なくなる多角形です

どうやって求めるの？ †

簡単O(N^4)の方法とめっちゃ効率のいいO(N log N)方法があります
他にもいろいろありますが省略します

簡単な方法は？ †

以下の手順で行います

1.適当な3点を選択します
2.1で構成された三角形の中に含まれている点をすべて削除します
3.点を一つ追加し新たな多角形を作ります
4.その多角形に含まれる点をすべて削除します
5.残っているすべての点が多角形を構成する点である場合、その多角形が凸包になります。点が残っている場合3へ戻ります

操作4においては多角形全体を探索しなくても、新たに追加した点と、それを結ぶ2点からなる3角形内に存在する点のみを探索すればよい

この手法では、計算誤差が発生する可能性があるので注意すること
ただし、実装が容易でなので単純なパターンでは便利です

めっちゃ効率のいい方法は？ †

まず、二つの凸包を考えます。このとき、
凸包Aのもっとも右側にある点が、凸包Bのもっとも左側にある点よりも左側にある
とします。

さて、この二つの凸包を合体させることを考えます。つまり凸包A、凸包Bを構成する全ての点の凸包Cを求めるということです
このときの凸包Cの作り方は凸包A,Bから上接辺、下接辺と呼ばれる辺を2つ引くことで求めることが出来ます

上接辺の求め方をいかに示します下接辺も同様の手順で求めることが出来ます

この2つの凸包を構成している点のうち最も高い位置にある点HA,HBを求めます。
このうち、より低い位置にある点が上接辺の一端になります(同値の場合、両者を結んだ線が上接辺になる)
ここではHA＞HBであるとしましょう。以下の手順で上接辺を求めます

ピポットを一つ用意します。このピポットは初期値として凸包Aのうち最も右側にある点を指すとします
(ピポットの指す点 = P)(ピポットの指す点に隣接する点のうち、より高い位置にある点 = P')(HB)の3点を考えます。
この時、ベクトルHB-P,HB-P'の二つのベクトルを考えます。このベクトル外積、すなわち
HB-P×HB-P' ＝ (|HB-P||HB-P'|)sinθが負(下向き)あるいは0であるとき、ピポットの指す点をP'に変更します
外積が正である場合はHB-Pが上接辺となります(下接辺の場合は外積が負の時にHB-Pが下接辺になります)
(また、HA＜HBの場合は上接辺の場合は外積が負の時にHA-Pが上接辺となり、下接辺の場合は正の時にHA-Pが下接辺となります)

さて、このようにして上接辺と下接辺を求めることで凸包Cを得ることが出来ました

そもそも凸包Aと凸包Bをどうやって求めるの？ †

与えられた細分化(すなわち各領域に存在する点の数が3以下になるように)します。点の数が3の時は凸包が三角形であることは自明です
このようにして再帰的に小さな凸包同士の合成を行うことで大きな凸包を得ます
このような手法を分割統治法と言い、O(nlog n)で計算できます(n は点の数)