On the stabbing number of a random Delaunay triangulation

Prosenjit Bose and Luc Devroye
Computational Geometry
Volume 36, Issue 2 , February 2007, Pages 89-105
http://dx.doi.org/10.1016/j.comgeo.2006.05.005

平面上で正の面積を持つコンパクト凸集合の中にn個の点を一様ランダム独立にばらまき，それらの点に対するDelaunay三角形分割を考える．
ある直線を考えて，それがこの三角形分割の辺のいくつと交わるか数える．
直線をいろいろと変えたときのこの交わりの数の最大値の期待値がΘ(√n)になることを証明している．
(裾確率の評価もしている．)
そして，この結果を計算幾何の様々なアルゴリズムの平均値解析に応用している．