The Geodesic Diameter of Polygonal Domains

Sang Won Bae, Matias Korman, Yoshio Okamoto
arXiv:1001.0695

自分の論文を紹介するのはあまり好きじゃないのですが，たまにはやります．

単純多角形の中に多角形の穴がいくつかある集合を「polygonal domain」と呼ぶのですが，その直径を計算するという話．
問題は単純だけど，いままで多項式時間アルゴリズムが知られていなかったので，真面目にやった，という話．
真面目にやった割に計算量が頂点数の7.73乗ぐらいとやたら大きいのはちょっと残念ですが，そもそもpolygonal domainに対する最短路検索とか無茶苦茶難しいので，仕方ないです．
アルゴリズム自体が主な結果ではなく，どちらかといえば，直径を与える点対がどこに位置するかによって，その対の間にいくつ最短路が存在しなければならないかということに対する下界を与えている部分が重要で，例えば，直径を与える点対が領域の内部 (interior) にある場合はその対の間に最短路が5つ以上ないといけない (最短なたどり着き方が5通り以上ある)，というのが主定理の一部分です．
それを証明するために，複数の凸関数のlower envelopeの構造を見ることになって，ここら辺はややこしくなってます．できるだけ読みやすく書いたつもりですが，そんなに読みやすいとも思えないんです．困ったものです．