起きたら昼すぎで、planarityをやりまくっていたら夜だった。変だな。

---

planarityのコツをつかんだ。なるべく長く、かつ「ループに含まれる全ての頂点についてループ上の隣以外の頂点に対する辺がない」ようなループを見つけると、それを外縁の凸包として使える。これを見つけられない場合は三角形の中に全てを入れることになり、不可能ではないが配置が苦しくなる。平面的グラフの特性というよりplanarityの仕様として、このような条件を満たす長めのループが必ずただ1つ用意されているようだ。

素早く解くコツとしては、最初から上記のようなループを見つけるのは難しいので、まずは適当なループを持ってきて凸包を作ってしまう。その後適当に交差を解消させていけば、大体どこかで良さげなループが見えてくるのでそれを外側に持ってくる。良いループが終盤で見つかった場合は大部分の頂点を動かす必要が出るので悲惨になる。

次数2の頂点を見つけた場合はめっけもんだ。このような頂点は必ず外側に持ってこれる。

このようなことを学んだ結果、n=20なら2分前後で解けるようになった。初期設定のn=8なら10秒前後、n=40なら8~10分前後でいける。

---

Vulkan入門の6-2を書き進めた。pipelineBarrierの説明にてこずっているが、明日には公開できると思う。

---

ジョギングをした。4.2km。