Official

G - Division Point Hull Editorial by KumaTachiRen


0-indexed で考えます。すなわち点が \(P_0,P_1,\dots,P_{N-1}\) であるとします。

この解説では以下の記法を用います。ただし \(A,B\) は点の集合、\(r\) は任意の実数とします。

  • \(\operatorname{conv}(A)\):\(A\) の凸包。\(\operatorname{conv}(\emptyset)=\emptyset\) とする
  • \(r\cdot A=\{r\cdot a\mid a\in A\}\)(\(r\cdot a\) は \(a\) を成分ごとに \(r\) 倍したもの)
  • \(A+B=\{a+b\mid a\in A,b\in B\}\):Minkowski 和(\(a+b\) は \(a,b\) を成分ごとに足し合わせたもの)

分割統治することを考えます。

\(P[l,r)\coloneqq\{P_i\mid l\leq i< r\},Q[l,r)\coloneqq\{Q_{i,j}\mid l \leq i\lt j\lt r\}\) とすると \(Q[l,l+1)=\emptyset\) であり、\(r-l\geq 2\) のとき \(m=\left\lfloor\frac{l+r}{2}\right\rfloor\) とすると以下が成り立ちます。

\[\begin{aligned} Q[l,r) &=Q[l,m)\cup Q[m,r)\cup\left\{\frac{q\cdot u+p\cdot v}{p+q} \mid u\in P[l,m),v\in P[m,r)\right\}\\ &=Q[l,m)\cup Q[m,r)\cup\left(\frac{q}{p+q}\cdot P[l,m)+\frac{p}{p+q}\cdot P[m,r)\right) \end{aligned}\]

\(q'=\frac{q}{p+q},p'=\frac{p}{p+q}\) として上式の両辺の凸包を考えると以下が成り立ちます(\(\operatorname{conv}(A+B)=\operatorname{conv}(A)+\operatorname{conv}(B)\) を用いています)。

\[\begin{aligned} \operatorname{conv}(Q[l,r)) &=\operatorname{conv}\bigl(Q[l,m)\cup Q[m,r)\cup\left(q'\cdot P[l,m)+p'\cdot P[m,r)\right)\bigr)\\ &=\operatorname{conv}\bigl(\operatorname{conv}(Q[l,m))\cup \operatorname{conv}(Q[m,r))\cup\operatorname{conv}\left(q'\cdot P[l,m)+p'\cdot P[m,r)\right)\bigr)\\ &=\operatorname{conv}\bigl(\operatorname{conv}(Q[l,m))\cup \operatorname{conv}(Q[m,r))\cup\left(q'\cdot \operatorname{conv}(P[l,m))+p'\cdot \operatorname{conv}(P[m,r))\right)\bigr) \end{aligned}\]

計算量を考えます。

\(n\) 点の凸包は \(O(n\log n)\) 時間で求められます。 また凸多角形同士の Minkowski 和は、辺ベクトルを偏角順で merge することで頂点数の和についての線形時間で求められます。 \(\operatorname{conv}(Q[l,r))\) の頂点数は \(O(r-l)\) になることが示せる(付録参照)ため、\(r-l=n\) のときに \(\operatorname{conv}(Q[l,r))\) を計算するための時間計算量を \(T(n)\) とおくと \(T(n)=2T(n/2)+O(n\log n)\) より \(T(n)=O(n(\log n)^2)\) となります。

従って求めたい凸包 \(\operatorname{conv}(Q[0,N))\) は \(O(N(\log N)^2)\) 時間で得ることができます。

面積は凸包の頂点数に対して線形時間で計算できます。実装ではすべての点の座標を \(p+q\) 倍すれば整数範囲で計算することができます。 実装例(C++)

\(\operatorname{conv}(Q[l,r))\) を直接計算せずに、分割統治の過程では \(q'\cdot \operatorname{conv}(P[l,m))+p'\cdot \operatorname{conv}(P[m,r))\) を計算してその頂点を集約しておき、最後にそれらのなす凸包を計算することでも \(O(N(\log N)^2)\) 時間で解くことができます。

また凸包計算において必要となる点のソートを分割統治の過程においてマージソートの要領で行うことで、凸包も線形時間で計算できるようになり全体 \(O(N\log N)\) 時間でも解くことができます。 実装例(C++)


付録:\(\operatorname{conv}(Q[l,r))\) の頂点数の評価

\(\operatorname{conv}(Q[0,N))\) の頂点数が \(O(N)\) であること、特に高々 \(3N\) であることを示します。

\(P_0,\dots,P_{N-1}\) のうち相異なる点の種類数を \(M\)、それらの点の凸包を \(C\) とします。 \(C\) の頂点のうち、\(P_0,P_1,\dots,P_{N-1}\) の中にちょうど \(1\) 回現れるものの個数を \(h_1\)、\(2\) 回以上現れるものの個数を \(h_2\)、また \(h=h_1+h_2\) とします。

\(\operatorname{conv}(Q[0,N))\) の頂点 \(x\) を任意にとったとき、凸包の性質から以下を満たすような単位ベクトル \(v\) が存在します。

  • \(\{Q_{i,j} \mid (i,j) \in \argmax_{(i,j)}(v\cdot Q_{i,j})\}=\{x\}\)
  • \(\#\{P_i \mid i\in\argmax_i(v\cdot P_i)\}=1\)

\(\{P_i \mid i\in\argmax_i(v\cdot P_i)\}\) が含む唯一の点を \(R\) とします。

まず \(\#\argmax_i (v\cdot P_i) \geq 2\) であるとき、\(i,j\in\argmax_i (v\cdot P_i), i<j\) をとると \(P_i=P_j=Q_{i,j}=R\) です。少なくとも一方の端点が \(R\) と異なる \(Q_{i',j'}\) に対して \(v\cdot Q_{i',j'}<v\cdot R\) が成り立つため、\(x=R\) が従います。このような \(x\) としてあり得る点は高々 \(h_2\) 個です。

次に \(\#\argmax_i (v\cdot P_i)=1\) であるとき、\(k\in \argmax_i (v\cdot P_i)\) とすると \(v\cdot Q_{i,j}\) を最大化する \((i,j)\) は必ず \(i,j\) のどちらかが \(k\) です(そうでなければ一方を \(k\) に置き換えることで \(v\cdot Q_{i,j}\) をより大きくできる)。

したがって、考えるべきものは次の \(2\) 種類です。

  • (A) \(i<k=j\) かつ \(v\cdot P_i=\max_{i'<k}(v\cdot P_{i'})\)
  • (B) \(i=k<j\) かつ \(v\cdot P_j=\max_{k<j'}(v\cdot P_{j'})\)

\(\operatorname{conv}(Q[0,N))\) の頂点である \(Q_{i,j}\) で、ある \(v\) に対して (A),(B) を満たす点の集合をそれぞれ \(A,B\) とします。

\(\#A\) を評価します。 \(C_k=\operatorname{conv}(P[0,k))\) とおきます。(A) における \(k\) として考える必要があるのは、\(P_k\) が \(C\) の頂点かつ \(P_0,\dots,P_{N-1}\) の中にその点が \(1\) 回だけ現れる場合のみであり、そのような \(k\) はちょうど \(h_1\) 個あります。 このような \(k\) について、\(C_k\) に \(P_k\) を追加して \(C_{k+1}\) を作ることを考えると、\(P_k\) は最終的な凸包 \(C\) の頂点なので \(C_k\) の外部にあり、\(P_k\) から見える \(C_k\) の境界は連続した頂点列になります。 また \(\argmax_i (v\cdot P_i)=\{k\}\) でなくてはならないことを踏まえれば、 (A) における \(P_i\) として考える必要のある点は、この頂点列上の点に限られます。

この頂点列の両端を除く頂点(図中の丸で囲まれた頂点)は、\(P_k\) を追加した時点で凸包の頂点でなくなり、それ以降も凸包の頂点にはなりません。逆に最終的な凸包 \(C\) の頂点はこのように消えることはありません。 したがって、すべての \(k\) を通して、これらの頂点列の内部に現れる相異なる点の総数は高々 \(M-h\) です。 一方、それぞれの頂点列の両端(図中の四角で囲まれた頂点)は高々 \(2\) 点であり、考えるべき \(k\) は \(h_1\) 個なので、両端として現れる点の個数は重複込みでも高々 \(2h_1\) 個です。 よって \(\#A\leq (M-h)+2h_1\) が得られます。 同様にして \(\#B\leq (M-h)+2h_1\) も得られます。

次に \(\#(A\cap B)\) を評価します。 \(C\) の辺のうち、以下の \(2\) 条件をともに満たすものを考えます。

  • 両端の点は \(P\) においてちょうど \(1\) 回ずつ現れる。
  • 辺の端点を除いた内部に、別の \(P\) の点が存在しない。

このような辺の両端を \(P_a,P_b\ (a<b)\) とします。辺の外向き法線ベクトルから少しだけ \(P_b\) 側に回転させた \(v\) を考えると、\(v\cdot P_b>v\cdot P_a>v\cdot P_i\ (i\neq a,b)\) が成り立ちます。よって \(Q_{a,b}\in A\) です。 逆に少しだけ \(P_a\) 側に回転させれば \(a,b\) が逆になり \(Q_{a,b}\in B\) が得られます。 したがって、この条件を満たす \(C\) の辺 \(1\) 本につき \(A\cap B\) の要素が \(1\) つ得られます。

\(C\) の辺は全部で \(h\) 本あり、このうち \(P\) に \(2\) 回以上現れる点を端点にもつ辺は高々 \(2h_2\) 本、また端点を除いた内部に別の \(P\) の点を含む辺は高々 \(M-h\) 本です。 よって上の \(2\) 条件をともに満たす辺は少なくとも \(\max(0,h-2h_2-(M-h))=\max(0,2h_1-M)\) 本あり、

\[ \#(A\cap B)\geq \max(0,2h_1-M) \]

が得られます。

以上をまとめると、\(\operatorname{conv}(Q[0,N))\) の頂点数を \(K\) としたとき

\[ \begin{aligned} K &\leq h_2+\#(A\cup B)\\ &= h_2+\#A+\#B-\#(A\cap B)\\ &\leq 2M+2h_1-h_2-\max(0,2h_1-M) \end{aligned} \]

が成り立ちます。この式において \(2h_1\leq M\) かどうかで場合分けすれば \(K\leq 3M\leq 3N\) が得られ,特に \(\operatorname{conv}(Q[0,N))\) の頂点数は \(O(N)\) です。

同じ議論を任意の区間 \([l,r)\) に適用できるため、\(\operatorname{conv}(Q[l,r))\) の頂点数も \(O(r-l)\) となります。

\(3N\) より小さな一般の上界が得られるか、あるいはこの上界に近いケースが構築できるかは分かっていません……。