河野真治 @ 琉球大学情報工学です。

訳は適当。mixi ねたです。
    http://www.planarity.net/game.php 
ですけど。

アルゴリズム理論的にはちょっと有名? あんまり興味ないので調べ
てませんが。グラフ的な制約と位置的な制約の両方があるので難し
いらしい。

このゲームの生成アルゴリズムだと非常に局所性の強いグラフが生
成されているので予定調和的に解けていくんだけど、一ヶ所はまる
ところがあります。 

それは「端っこでない点を端に置くと回り込む点が多数出て収集が
つかなくなること」。で、3点あるいは2点としか繋がってない点は
端っこであることが多いので、それから始めると良いみたい。そこ
で、「前線」既に終わった部分とそうでない部分の境界線が出来る
んだよね。それを一つ一つ動かして行けばできる。ということはO(
n)。実際、そういうアルゴリズムがあるらしい。なんだけどワーク
スペースを開けるために、既に作った部分を圧縮するという作業が
必要。最初に円形に並んでいるからそれをどけなきゃならん。これ
はΣnなので結局O(n^2)。そりゃ時間かかるわ。確かに間を詰めて
いる時間が大半だった... 

で、ふっと考えてみると、どっか任意の閉空間をドーナッツの穴と
考えると、そのまま裏っ返せるはずだよね。で、裏っ返しに解いて
行けば回り込みは存在しない。しかも、隣接する閉空間の大きさは
それほど大きくないことが多いので試行錯誤が少ないはず。しかも、
外から内に解くので場所あけの再配置が少なくなるはず。 

で、やってみると割とうまくいくみたい。ただ最初に選ぶ長方形に
よっては点の分布が方よってしまうみたいね。で、偏ると端っこか
ら解いていくのとほとんど変わらない。端っこを探すのが、あまり
難しくないだけに、実はだめな方法な気がして来ました。

出来ない場合は、特定の局所的なパターンがあるらしい。ってこと
は、ランダムに作成したグラフだと平面化できる確率はかなり小さ
いってことか。点が多ければ、ほとんどすべての局所パターンが出
現すると考えるのが妥当だろうから。

出来ない部分は局在化できるらしいので、それを見つけたら削除で
きるという風にすると難しさが上がるんじゃないかな。

---
Shinji KONO @ Information Engineering, University of the Ryukyus
河野真治 @ 琉球大学工学部情報工学科