小特集 8. CAT(0)空間上のアルゴリズムと最適化について

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.101 No.3 (2018/3) 目次へ

前の記事へ次の記事へ


グラフアルゴリズムの最先端

小特集 8.

CAT(0)空間上のアルゴリズムと最適化について

Algorithm and Optimization on CAT(0)-space

平井広志

平井広志 東京大学大学院情報理工学系研究科数理情報学専攻

Hiroshi HIRAI, Nonmember (Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, 113-8656 Japan).

電子情報通信学会誌 Vol.101 No.3 pp.276-279 2018年3月

©電子情報通信学会2018

abstract

 CAT(0)空間と呼ばれるユークリッド空間や双曲空間を一般化した距離空間がある.CAT(0)とは,「曲率が非正」ということを意味している.この空間は,ユークリッド空間で成り立つ様々な良い性質を引き継いでいる.特に,任意の2点を結ぶ測地線(math最短路)が一意に定まる.このことから凸関数なども自然に定義される.最近になって,CAT(0)空間を利用したモデリングやその上でのアルゴリズム・最適化理論が展開され始めている.本稿では,そのような試みの一端を紹介する.

キーワード:CAT(0)空間,測地線問題,系統樹空間,メディアングラフ,オーソスキーム複体

1.は じ め に

 CAT(0)空間と呼ばれる距離空間がある.CATは3人の数学者Cartan, Alexandrov, Toponogovの頭文字であり,0は曲率が0以下を意味している.この空間は,Gromov(1)によって導入され,幾何学的群論という分野において重要な役割を果たしている.最近になって,CAT(0)空間を利用したモデリングやその上でのアルゴリズム・最適化理論が展開され始めている.本稿では,そのような試みの一端を紹介する.

2.CAT(0)空間の定義

 距離空間mathのパスmathの長さmath

math

(1)

と定義する.ここでsupは区間分割mathmathについてとる.2点mathmathを結ぶ測地線とは,一定のスピードで進むパスmathであって,mathmath,そして,mathとなるものである.任意の2点に対し測地線が存在する距離空間を測地的距離空間という.


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録


  

電信情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌 会誌アプリのお知らせ

電信情報通信学会 - IEICE会誌アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。