NO_WAIT

主にプログラミング

三角形内のランダムな点列の凸包と調和数の関係を可視化

計算幾何学の基本的要素である凸包について調べていたおり、それについていくつか興味深い文書を見つけました。 特定の種類の領域内で一様に分布する点を包む凸包の長さの期待値を評価する、そんな内容です。 その中で、三角形領域内のランダムな点列がつくる凸包の長さと調和数(調和級数の部分和)との関係を証明したものがありました。 こんなところにも調和数、と興味を持って、JavaScriptで可視化してみました。

このプログラムは、三角形領域内でランダムに生成した点について凸包を計算し、 その長さを点の数\(n\)に対してプロットすることを周期的に繰り返します。 (頂点のドラッグによって三角形は変形できます。) 背景の黄色い棒グラフが調和数の2倍となっています。 確かに、計算した凸包の長さはこれに近くなっています。

計算して確かめる。

レポートRuler, compass, and computer : the design and analysis of geometric algorithms によれば、平面上の任意の三角形内で一様に分布するランダムな点列がつくる凸包の長さは、次の期待値を持ちます:

\[ \bar{h}{(n)} = 2 H_{n - 1} = 2\left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n - 1} \right) \]

レポート中の証明によると、 \(\bar{h}{(n)}\) は次の積分と一致することが示されます。この積分は計算すると上の式に一致します。

\[ \bar{h}{(n)} = 4 {n \choose 2} {\int_0^1 {\int_0^1 {((uv)^{n - 2} + (1 - uv)^{n - 2})uv} du}dv} \]

この積分を実際に計算するSageワークシートを作りました。 The Expected Number of Vertices in a Convex Hull of Random Points in a Triangle 積分はscipy.integrate.nquadを利用しています。

所感

調和数というのはどんな所に現れるかわからない面白さがあります。 以前に調べたBook Stacking Problemもそうです。 ところで、ランダムな点列の凸包ってどんな応用があるんでしょう?こればかりは想像もつきません。

今回、Sageで計算するのにSageMathCloudを利用させていただきました。 Sageワークシートをブラウザ上で作成・実行でき、簡単に公開できます。 Pythonで書いたコードをすぐに走らせて結果を得るだけでなく、MathJaxによる数式表示、 Markdown記述も可能で、実行可能な数学ノートとして活用できそうです。 本当に便利な世の中になりました。

参考