Extreme Elevation on a 2-Manifold

Pankaj K. Agarwal, Herbert Edelsbrunner, John Harer and Yusu Wang
Discrete and Computational Geometry
Volume 36, Number 4 / December, 2006
Pages 553-572
http://dx.doi.org/10.1007/s00454-006-1265-8

SoCG2004特集号から．
計算トポロジー (computational topology) の論文．

連結コンパクト2次元多様体Mとその上のMorse関数fを考える．
関数fのレベル集合M(a)={x∈M | f(x)≦a}を考えると，aが大きくなるにつれてそのトポロジーが変化し，その変化が訪れるのは臨界点に達したときである．
連結成分が増えるのは極小点に達したときで，その成分は鞍点に達したとき他の成分と併合する．
また，穴ができるのは鞍点に達したときで，その穴は極大点に達したとき消滅する．
1つの鞍点が成分の併合と穴の消滅のどちらか一方にしか貢献できないので，これによって臨界点のペアを作ることができる．
これはEdelsbrunner, Letscher and Zomorodian (2002) が提案したtopological persistenceの概念の要約である．
しかし，このようにペアを作ると，はじめに現れる極小点，最後に現れる極大点や，Mの種数がgのときg個のサイクルに対応する2g個の鞍点の合計2+2g個の臨界点はペアにならないまま残されてしまう．

そこでこの論文では，Cole-McLaughlin, Edelsbrunner, Harer, Natarajan, and Pascucci (2004) によるReebグラフを用いて，全ての臨界点をペアにできるようにpersistenceの概念を拡張している．

そして，考えている2次元多様体Mが3次元空間に滑らかに埋め込まれている場合を考える．
このときにMの点xのelevationという概念を導入している．
これはxを臨界点とするような方向のMorse関数 (これは向きを除いて一意) を考えて，そのときにペアとなる臨界点とのそのMorse関数値の差 (の絶対値) とするのである．
このelevationは埋め込みを平行移動させたり，回転させたりしても不変であることがうれしい．
しかし，elevationはM上で連続であるとは限らず，なかなか複雑な振舞を見せる．
そのような特異性について本文では論じられている．

またelevationの極大点に関して考察が行なわれていて，4種類の極大点が存在することが示されている．
そして，全ての極大点を列挙するアルゴリズムも与えられている．
一応，入力の多項式時間の計算量ではあるけれどもO(n^5 log n)ということなので，まだまだ改善の余地はありそうだ．

この研究はバイオインフォマティクスのタンパク質のdockingから来ている．
タンパク質を構成する原子を球でモデル化するとタンパク質自身は球の合併になり，これはだいたい多様体と見なせる．
2つのタンパク質がどのようにdockingするのか解析したり予測したりするわけだけれども，そのときに多様体のトポロジー的構造を計算する必要が出てくる．
そのため上記のような計算トポロジーの技法が最近盛んに研究されているようである．