線分は二つの端点によって一意に決まる.
平面上の2つの線分を考えると以下の3つの可能性がある,
共有点が0個のケース, 共有点が1個のケース, 無限に多くの共有点を持つケース.
さらに, 2つの線分が共有点を1つのみ持つとき, 共有点がどちらかまたは両方の線分の端点である場合がある. もし共有点がどちらの線分の端点でもないなら, その点は両方の線分の内部の点である.
もし, 線分 L1 と L2 の共有点Tが L1 と L2 の唯一の共有点であり, 両方の線分の内部の点であるとき, Tを真の交点と呼ぶことにする.
3つの線分 L1, L2, L3 を考える.
L1: (27, 44) から (12, 32)
L2: (46, 53) から (17, 62)
L3: (46, 70) から (22, 40)
L2 と L3 は真の交点を持つことが確かめられる. L3 の1つの端点の(22,40)は L1 上にあるが, これは真の交点とならないことに注意. L1 と L2 は共有点を持たない. つまり上の, 3つの線分では, 真の交点は1つとなる.
いま, 同じことを5000個の線分に対して行うことにする. そのために, 20000個の数を"Blum Blum Shub"と呼ばれる擬似乱数生成法によって生成する.
s0 = 290797
sn+1 = snsn (modulo 50515093)
tn = sn (modulo 500)
それぞれの線分を4つの連続する tn によって決める. つまり, 最初の線分は,
(t1, t2) から (t3, t4) と与えられる.
最初の4つの数は上の生成法によって, 27, 144, 12, 232 となる. 最初の線分は, (27,144) から (12,232) となる.
上の5000個の線分に対して, いくつの相異なった真の交点が存在するか?