Randomized Algorithms for Computational Geometry

とりあえずいくつか面白い論文をみつけた

Randomized Incremental Construction of Delaunay and Voronoi Diagrams

Randomized Algorithms for Geometric Optimization Problems

An Introduction to Randomization in Computational Geometry

ひとつ読んだのでまとめる。

randomized algorithm for slope selection

問題

二次元平面上に点ある。このうち2点を選んで直線を引く時、番目に小さい傾きを求めよ。

双対問題

点を直線に写し、直線をに写す操作を考えると、問題は以下と等価になる。

2次元平面上の本のnon-verticalな直線について、それらの交点のうち、座標が番目に小さいものを求めよ。

簡単のため、どの3直線も1点で交わらないとし、どの2直線同士も同じ座標で交わらないとする。

考察

答えの座標がの区間に存在するとする。このとき、軸に平行な帯を考え、における直線の順序とにおける直線の順序を考える。前者の順序をとし、後者をとすると、かつのとき、またそのときに限り2直線は交わる。つまり区間内にいくつ交点があるかはこの順列の点灯数を求まることで決まる。

これを何度か繰り返して区間を狭めていくことができるが、乱択と組み合わせるともうすこし賢くできるらしい。