読者です 読者をやめる 読者になる 読者になる

凸包の頂点数の話

まとめ

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:辺を反時計回りにベクトルで持つとすると、一番下から一番右の部分

広告を非表示にする