凸包の頂点数の話

$m\times m$ のグリッドに収まる格子点を頂点とする凸多角形の頂点数は $O(m^{2/3})$ 。
詳しい話は論文を読んでください。
On the maximal number of edges of convex digital polygons included into an m × m-grid

凸包を取ると考慮すべき点の数が減って嬉しい、という問題が競プロでたまに出題されます。
この類の問題の解説で頂点数のオーダーが $O(\sqrt{m})$ と書いてあることがある*1のですが、実際は $O(m^{2/3})$ だよという話です。*2

頂点数を大きくするにはマンハッタン距離が短い辺から使うのが最適です。
マンハッタン距離が $n$ 以下の辺を使うと、頂点数が $\Theta(n^2)$ の凸多角形が $\Theta(n^3)$ のグリッドに収まります。

めんどうなので、成分が正の部分だけ考えます。*3
そうすると使う辺は(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),...となります。
これを角度でソートして並べると凸多角形の右下部分になります。
本当は成分が互いに素な辺だけを使う必要がありますが、とりあえず無視します。

マンハッタン距離が $n$ 以下の辺を全て使う場合、各座標の総和は
$\sum_{i=1}^{n-1} i(n-i)=(n-1)n(n+1)/6$
となります。

辺の数は
$\sum_{i=1}^{n-1}i=(n-1)n/2$
となります。

グリッドのサイズが $\Theta(n^3)$ 、頂点数が $\Theta(n^2)$ なので、 $m\times m$ のグリッドに $\Theta(m^{2/3})$ 頂点の凸多角形を収めることができています。

上の計算では成分が互いに素でない辺まで使っていましたが、互いに素である確率は定数なので、これを使わないようにしてもオーダーは変わりません。
互いに素 - Wikipedia

*1:どうやら蟻本の誤りに起因するらしい

*2:Codeforcesの記事で見たはずなんですがURLがわからなくなった

*3:辺を反時計回りにベクトルで持つとすると、一番下から一番右の部分