著者

荒井 迅

出版者

ERATO湊離散構造処理系プロジェクト

巻号頁・発行日

2011-06

---

位相幾何学とは、空間をぐにゃぐにゃと連続変形しても不変な性質を研究する数学であり、様々な数学の分野で重要な道具となっている。近年、より現実的な問題に位相幾何学を応用するために、計算機を用いて位相不変量を計算するアルゴリズムの開発が活発になっており、本講演ではその中の一つである計算ホモロジー理論について、その基礎とセンサーネットワークの被覆問題への応用について解説する。センサーネットワークにおいては、大量のセンサー、例えば人間の存在を感知したり、温度を測定するセンサーがあちこちにばらまかれた状況を考える。このとき、センサーたちの感知領域が、正しく目的の領域を被覆しているか、すなわちどこかに見逃しがないか、という問題が重要になる。GPSなどを用いて各センサーの位置情報を求めれば計算幾何を用いることが出来るが、消費電力を小さくおさえるためには、なるべく少ない情報で解決したい。R.Ghristらの研究により、センサーネットワークから定義されるRis複体のホモロジーを計算すれば、この被覆問題を少ない情報で綺麗に記述できる事がわかったのだが、今度は「Rips複体のホモロジーをいかに小さいコストで計算するか」という問題が生じた。この問題に対し、林和則、平岡裕章両氏との共同研究で得られた、マイヤービートリス系列を用いて分散計算をするアプローチと、Ali Jadbabaieらが進めているネットワーク上のラプラシアンを用いたアプローチを紹介する。