|
電子情報通信学会 - IEICE会誌 試し読みサイト
© Copyright IEICE. All rights reserved.
|
|
|
電子情報通信学会 - IEICE会誌 試し読みサイト
© Copyright IEICE. All rights reserved.
|
グラフアルゴリズムの最先端
小特集 8.
CAT(0)空間上のアルゴリズムと最適化について
Algorithm and Optimization on CAT(0)-space
abstract
CAT(0)空間と呼ばれるユークリッド空間や双曲空間を一般化した距離空間がある．CAT(0)とは，「曲率が非正」ということを意味している．この空間は，ユークリッド空間で成り立つ様々な良い性質を引き継いでいる．特に，任意の2点を結ぶ測地線（
最短路）が一意に定まる．このことから凸関数なども自然に定義される．最近になって，CAT(0)空間を利用したモデリングやその上でのアルゴリズム・最適化理論が展開され始めている．本稿では，そのような試みの一端を紹介する．
キーワード：CAT(0)空間，測地線問題，系統樹空間，メディアングラフ，オーソスキーム複体
CAT(0)空間と呼ばれる距離空間がある．CATは3人の数学者Cartan, Alexandrov, Toponogovの頭文字であり，0は曲率が0以下を意味している．この空間は，Gromov(1)によって導入され，幾何学的群論という分野において重要な役割を果たしている．最近になって，CAT(0)空間を利用したモデリングやその上でのアルゴリズム・最適化理論が展開され始めている．本稿では，そのような試みの一端を紹介する．
距離空間
のパス
の長さ
を
(１)
と定義する．ここでsupは区間分割
についてとる．2点
，
を結ぶ測地線とは，一定のスピードで進むパス
であって，
，
，そして，
となるものである．任意の2点に対し測地線が存在する距離空間を測地的距離空間という．
続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。
電子情報通信学会 - IEICE会誌はモバイルでお読みいただけます。
電子情報通信学会 - IEICE会誌アプリをダウンロード
