■

2次元座標上に点が散乱している。ある点から、すぐ「上」にある点を一つ見つけるにはどうすればよいか？例えば(0,0)(1,5)(7,2)(-4,6)(-1,12)の場合、(0,0)からすぐ上にある点は多分だれが選んでも(1,5)になるであろう。また、(-1,12)の場合、すぐ上の点は存在しないという答えになるだろう。これを一般的な点の集まりであった場合、全ての点にとってすぐ「上」および「右」「左」「下」を見つけるにはどういうアルゴリズムにすればよいか？また、以下のような条件も存在する。

• 人間が直感的に見みた場合の、すぐ「上」「下」「左」「右」となるべく一致すること。
• ある点Ａにとってすぐ上の点がＢであったとしてもＢのすぐ下の点がＡである必要はない。
• ある点ＡにとってＢがすぐ上でもすぐ右であるような状態であってもかまわない。
• ある点からすぐ「上」「下」「右」「左」のどれかに飛んで他の点に行けるとする。これを繰り返した場合、全ての点にかならずたどり着けるように「上」「下」「右」「左」を選ぶ。

さて、どうだろうか？これ、意外に難しい。最後の条件を満たすのがとにかく難しい。さらに、条件をみたしているかどうかの証明も難しい。例えば、サイコロの５のような配列を考えてみると、各四隅の点が真ん中のを「上」「下」「左」「右」と見なす可能性は低いであろう。そのばあい、真ん中の点にたどり着くことはできず、４番目の条件をみたさない。なので、最低でも、４隅の点のどれかが「上」「下」「左」「右」と見なしてくれるアルゴリズムでなくてはいけない。

さて、だれか挑戦者求む（ぉ