まず \(K=1\) の場合を考えます。

\(N\) 点の凸包はその表面を構成する( \(3\) 次元空間上の)三角形の集合として表すことができます。そのような三角形のリストは \(O(N^2)\) 時間で求めることができます。またその結果得られる三角形の個数はオイラーの多面体定理より \(O(N)\) です。

凸包に含まれる格子点の個数は以下のように \(O(N M^2 )\) 時間で求めることができます( \(M := \max \{|x_i|,|y_i|,|z_i| \}\) )。

• \(-M \le x,y \le M\) の範囲で \(x,y\) を固定する
  • このとき凸包と決めた \(X,Y\) 座標の共通部分は \(Z\) 軸と平行な線分か空集合になる
• 各三角形と決めた \(X,Y\) 座標の共通部分を調べ、線分の端点を求める
  • 端点は有理数になる
  • 時間計算量 \(O(N)\)
• 線分に含まれる格子点の数を数える。
  • 時間計算量　\(O(1)\)
  • 同様に境界の格子点も数えることができる

次に一般の \(K\) について考えるのですが、実は( \(t\) 倍に拡大した凸包に含まれる格子点の個数)　は \(t\) について \(3\) 次多項式になることが知られています(エルハート多項式)。

• 詳しくはこちらを御覧下さい https://trap.jp/post/1701/

また、その多項式 \(L_{\mathcal{P}}(t) = c_3t^3 + c_2t^2 + c_1t + c_0\) について

• \(c_3\) は多面体の体積と一致する
• \(c_0 = 1\)
• \(L_{int(\mathcal{P})}(t) = (-1)^3 L_{\mathcal{P}}(-t)\)

であることが知られており、凸包 \(\mathcal{P}\) の体積を \(V\) ,内部に含まれる格子点の数を \(I\) ,境界に含まれる格子点の数を \(B\) とすると

• \(c_3 = V\)
• \(c_3 + c_2 + c_1 + c_0 = I+B (=L_{\mathcal{P}}(1))\)
• \(c_0 = 1 (=L_{\mathcal{P}}(0))\)
• \(-c_3 + c_2 - c_1 + c_0 = -I = (L_{\mathcal{P}}(-1))\)

が成り立つので、これを解いて各係数を求めるとエルハート多項式が求まります。

得られた多項式に \(K\) を代入することで答えを求めることができます。総時間計算量は \(O(N^2 + NM^2)\) です。

実装例(C++)

\(2\) 次拡大や \(3\) 次拡大に含まれる格子点の数を数えて多項式補間をすることでもエルハート多項式を求めることもできます。実行速度が速い言語ではこちらでもACすることができます。