最近の研究から

計算幾何学の新展開

ロバスト幾何アルゴリズム

立体形状の表現と操作


勢力圏図を利用したスポーツチームワーク解析 (共同研究者 西田徹志,藤村光)

 ホッケーやサッカーの試合のビデオから選手の動きを抽出し, それぞれの選手の勢力圏の変化を調べることにより,各選手の チームワークへの貢献度を定量化しようと試みている.多人数 スポーツを観戦するための新しい支援システムの提供が目標で ある.

「超図形」の発見とその利用 (共同研究者 今井敏行,畑口剛,M.-S. Kim)

 合成積に関する逆元をもつように関数の世界を拡大すると 超関数が 生まれるのと同じように,ミンコフスキー和に 関する逆元をもつように 図形の世界を拡大すると「超図形」 が生まれることを発見した. この超図形を使うと,図形のミンコフスキー代数が著しく簡単になる.  
 現在,超図形の性質と応用の可能性を調べている.

発表論文


ボロノイ図を利用した近傍探索法 (共同研究者 神田毅)

 平面上に与えられた点集合に対するボロノイ図をあらかじめ作っておき, それを利用した各種の探索アルゴリズムを開発している.探索領域が円の 場合,幅一定の折れ線の場合,任意の単連結多角形の場合などに対する アルゴリズムを設計し,その有効性を実験的にも確かめることができた.

発表論文


4次元凸包のロバスト算法

 4次元ユークリッド空間に配置された有限個の点に対する凸包を 構成するための分割統治型算法を,整数帰着法と記号摂動法を 組み合わせることによってロバストなソフトウェアとして実装した. 4次元凸包は,3次元ドロネー四面体分割,3次元ラゲール四面体分割 の計算に利用できる.この性質を用いて,3次元領域の四面体 メッシュ分割の方法などを研究している.

発表論文


直線アレンジメントのロバスト算法 (共同研究者 D. Fogaras)

 平面上に与えられた有限個の直線に対して,そのアレンジ メント構造のロバストな計算法を設計し,その性能を計算実験 でも確かめた.ここでは,私たちが開発してきたロバスト幾何 アルゴリズム設計法である「位相優先法」を利用している.

発表論文


円ボロノイ図のロバスト算法 (共同研究者 D.-S. Kim)

 点ボロノイ図から出発し,局所的に辺の接続構造を変更すること によって円ボロノイ図を作るアルゴリズムを設計し,それをロバスト なソフトウェアとして実装した.これは,整数帰着法と記号摂動法を 用いたロバストな点ボロノイ図構成算法を利用している.

発表論文


図形の中心軸の安定な抽出法 (共同研究者 坂井秀行)

図形の中心軸は,図形の境界が複雑な細部構造をもつとき, 多くの「ひげ」状の枝をもってしまう.この中から,図形の 大域的構造を反映した大域的中心軸を安定かつ簡単に抽出する 方法を構成した.

発表論文


従来より連続性の高い多次元補間法 (共同研究者 日吉久礎)

多次元空間に配置された点を補間する超曲面はボロノイ図を 利用して作ることができるが,従来の方法(たとえばSibsonの方法) では,ドロネー超球面での連続性に限界があった.ここでの 連続性をいくらでも高めることのできる無限に多くの補間公式 を生成する一つの一般原理を見つけた.

発表論文


球面ラゲールボロノイ図

 ラゲール距離に基づいたラゲールボロノイ図と類似の分割図形が 球面上でも定義できることを示し,そのロバストな構成アルゴリズム も作った.

発表論文


混合演算による厳密計算の加速法 (共同研究者 神田毅)

 幾何計算を矛盾なく行うための厳密計算法は,多倍長計算を要する ために計算時間が大きい.これを減らすためには,まずは通常の 浮動小数点方式で計算し,精度が足りないとわかったときだけ多倍長に 切り換える混合演算が有効である.この混合演算の諸方式を比較し, 場面に応じて最適な方式を選択するための指針を作りつつある.

発表論文


投影図を利用した多面体の新しい表現法 (共同研究者 L. Ros, F. Thomas)

 3次元多面体を,2次元投影図と4頂点の高さによって表現する 立体表現法を提案した.この表現から立体を復元する際の誤差 の影響をできるだけ小さくする方法を構成することができた.

発表論文


細分割曲面を利用した立体形状データの圧縮 (共同研究者 川原田寛)

 比較的単純な多面体に細分割を及ぼすと複雑な形状が得られる ことを利用して,与えられた立体に近い細分割曲面が得られる ように細分割前の多面体を調整し,それを圧縮表現とみなす 圧縮法を提案し,その性能を実験的に確認しつつある.

発表論文


大域的滑らかさを重視した補間曲面生成法 (共同研究者 室谷浩平)

 空間に与えられた点群を通過する大域的に滑らかな曲面の表現法を 開発中である.曲率の2重和を全域で最小にする方針をとっているため, 不要なうねりなどの発生を防ぐことができる.ただし,局所的に形を 決めるわけではないので,従来の方法より大規模な連立方程式を 解かなければならない.

発表論文


結晶 ボロノイ図の近似算法とその応用 (共同研究者 小林景)

 空間に与えられた点群を通過する大域的に滑らかな曲面の表現法を 開発中である.曲率の2重和を全域で最小にする方針をとっているため, 不要なうねりなどの発生を防ぐことができる.ただし,局所的に形を 決めるわけではないので,従来の方法より大規模な連立方程式を 解かなければならない.

発表論文


多面体メッシュのための透し埋込み法 (共同研究者 室谷浩平)

 3次元多面体の表面を表すメッシュデータに透かしを安定に埋め込む 方法を研究している.この方法は,メッシュの頂点列の自己相関に 対するスペクトル分解を利用するものである.この方法では,透かしを 埋め込むための乱数表の任意性を,数値的安定化を図るために利用する ことができ,その結果,合同変換などの多面体の基本操作に対して ロバスト性をもっている.

発表論文


杉原厚吉のホームページへ