最近の研究から
計算幾何学の新展開
ロバスト幾何アルゴリズム
立体形状の表現と操作
勢力圏図を利用したスポーツチームワーク解析
(共同研究者 西田徹志，藤村光)
ホッケーやサッカーの試合のビデオから選手の動きを抽出し，
それぞれの選手の勢力圏の変化を調べることにより，各選手の
チームワークへの貢献度を定量化しようと試みている．多人数
スポーツを観戦するための新しい支援システムの提供が目標で
ある．
「超図形」の発見とその利用 (共同研究者 今井敏行，畑口剛，M.-S. Kim)
合成積に関する逆元をもつように関数の世界を拡大すると
超関数が 生まれるのと同じように，ミンコフスキー和に
関する逆元をもつように 図形の世界を拡大すると「超図形」
が生まれることを発見した．
この超図形を使うと，図形のミンコフスキー代数が著しく簡単になる．
現在，超図形の性質と応用の可能性を調べている．
発表論文
-
Kokichi SUGIHARA, Toshiyuki IMAI and Takeshi Hataguchi:
An algebra for slope-monotone closed curves.
International Journal of Shape Modeling, Vol.3, Nos.3&4
(September & December, 1997), pp.167-183.
-
Myung-Soo KIM and Kokichi SUGIHARA:
Minkowski sums of axis-parallel surfaces of revolution defined
by slope-monotone closed curves.
IEICE Transactions on Information and Systems,
Vol.E84-D, No.11 (2001), pp.1540-1547.
-
Kokichi SUGIHARA:
Invertible Minkowski sum of polygons.
10th International Conference on Discrete Geometry for
Computer Imagery (April, 2002), pp.350-359.
(Lecture Notes in Computer Science, 2301)
-
Kokichi SUGIHARA:
Hyperpolygons generated by the invertible. Minkowski sum of polygons.
Pattern Recognition Letters (to appear).
ボロノイ図を利用した近傍探索法 (共同研究者 神田毅)
平面上に与えられた点集合に対するボロノイ図をあらかじめ作っておき，
それを利用した各種の探索アルゴリズムを開発している．探索領域が円の
場合，幅一定の折れ線の場合，任意の単連結多角形の場合などに対する
アルゴリズムを設計し，その有効性を実験的にも確かめることができた．
発表論文
-
Takeshi KANDA and Kokichi SUGIHARA:
Comparison of various trees for nearest-point search
with/without the Voronoi diagram.
Information Processing Letters, Vol.84, pp.17-22. (2002).
-
Takeshi KANDA and Kokichi SUGIHARA:
Two-dimensional range search based on the Voronoi diagram.
V. Kumar, M. L. Gavrilova, C. J. K. Tan and P. L'Ecuyer (eds.):
Computational Science and Its Applications --ICCSA 2003,
Part III, Lecture Notes in Computer Science, 2669
(International Conference, Montreal, Canada, Proceedings)
pp.776--786 (2003).
４次元凸包のロバスト算法
4次元ユークリッド空間に配置された有限個の点に対する凸包を
構成するための分割統治型算法を，整数帰着法と記号摂動法を
組み合わせることによってロバストなソフトウェアとして実装した．
4次元凸包は，3次元ドロネー四面体分割，3次元ラゲール四面体分割
の計算に利用できる．この性質を用いて，3次元領域の四面体
メッシュ分割の方法などを研究している．
発表論文
-
Kokichi SUGIHARA:
Exact computation of 4-D conves hulls with perturbation and
acceleration.
Hyper Space, Vol.10, No.1 (2001), pp.68-86.
直線アレンジメントのロバスト算法
(共同研究者 D. Fogaras)
平面上に与えられた有限個の直線に対して，そのアレンジ
メント構造のロバストな計算法を設計し，その性能を計算実験
でも確かめた．ここでは，私たちが開発してきたロバスト幾何
アルゴリズム設計法である「位相優先法」を利用している．
発表論文
-
Daniel FOGARAS and Kokichi SUGIHARA:
Topology-oriented construction of line arrangements.
IEICE Transactions of Fundamentals of Electronics,
Communications and Computer Sciences, Vol.E85-A, No.5 (2002)
円ボロノイ図のロバスト算法
(共同研究者 D.-S. Kim)
点ボロノイ図から出発し，局所的に辺の接続構造を変更すること
によって円ボロノイ図を作るアルゴリズムを設計し，それをロバスト
なソフトウェアとして実装した．これは，整数帰着法と記号摂動法を
用いたロバストな点ボロノイ図構成算法を利用している．
発表論文
-
Deok-Soo KIM, Donguk KIM and Kokichi SUGIHARA:
Voronoi diagram of a circle set from Voronoi diagram of
a point set, I, Topology.
Computer Aided Geometric Design, Vol.18 (2001), pp.541-562.
-
Deok-Soo KIM, Donguk KIM and Kokichi SUGIHARA:
Voronoi diagram of a circle set from Voronoi diagram of
a point set, II, Geometry.
Computer Aided Geometric Design, Vol.18 (2001), pp.563-585.
図形の中心軸の安定な抽出法 (共同研究者 坂井秀行)
図形の中心軸は，図形の境界が複雑な細部構造をもつとき，
多くの「ひげ」状の枝をもってしまう．この中から，図形の
大域的構造を反映した大域的中心軸を安定かつ簡単に抽出する
方法を構成した．
発表論文
-
坂井秀行，杉原厚吉:
図形の中心軸の安定した生成法.
電子情報通信学会論文誌，
Vol.J85-D-II, No.11 (2002), pp.1637-1644.
従来より連続性の高い多次元補間法 (共同研究者 日吉久礎)
多次元空間に配置された点を補間する超曲面はボロノイ図を
利用して作ることができるが，従来の方法（たとえばSibsonの方法）
では，ドロネー超球面での連続性に限界があった．ここでの
連続性をいくらでも高めることのできる無限に多くの補間公式
を生成する一つの一般原理を見つけた．
発表論文
-
Hisamoto HIYOSHI and Kokichi SUGIHARA:
Improving continuity of Voronoi-based interpolation over Delaunay
spheres.
Computational Geometry - Theory and Applications,
Vol.22 (2002), pp.167-183.
球面ラゲールボロノイ図
ラゲール距離に基づいたラゲールボロノイ図と類似の分割図形が
球面上でも定義できることを示し，そのロバストな構成アルゴリズム
も作った．
発表論文
-
Kokichi SUGIHARA:
Laguerre Voronoi diagram on the sphere.
Journal for Geometry and Graphics,
Vol.6, No.1 (2002), pp.69-81.
混合演算による厳密計算の加速法 (共同研究者 神田毅)
幾何計算を矛盾なく行うための厳密計算法は，多倍長計算を要する
ために計算時間が大きい．これを減らすためには，まずは通常の
浮動小数点方式で計算し，精度が足りないとわかったときだけ多倍長に
切り換える混合演算が有効である．この混合演算の諸方式を比較し，
場面に応じて最適な方式を選択するための指針を作りつつある．
発表論文
-
Takeshi KANDA and Kokichi SUGIHARA:
Hybrid arithmetic for acceleration of geometric algorithms
---Suitable error estimation for each of sign decisions.
6th Korea-Japan Joint Workshop on Algorithms and Computation
(June 28-29, 2001, Pusan), pp.37-44.
投影図を利用した多面体の新しい表現法
(共同研究者 L. Ros, F. Thomas)
3次元多面体を，２次元投影図と4頂点の高さによって表現する
立体表現法を提案した．この表現から立体を復元する際の誤差
の影響をできるだけ小さくする方法を構成することができた．
発表論文
-
L. LOS, K. SUGIHARA and F. THOMAS:
Shape representation using trihedral mesh projection.
Visual Computer, Vol.19, Nos.2-3 (2003), pp.139-150.
細分割曲面を利用した立体形状データの圧縮
(共同研究者 川原田寛)
比較的単純な多面体に細分割を及ぼすと複雑な形状が得られる
ことを利用して，与えられた立体に近い細分割曲面が得られる
ように細分割前の多面体を調整し，それを圧縮表現とみなす
圧縮法を提案し，その性能を実験的に確認しつつある．
発表論文
-
Hiroshi KAWAHARADA and K. SUGIHARA:
Compression of arbitrary mesh data using subdivision surface.
10th IMA Conferences on the Mathematics of surfaces,
Leeds, September 15-17, 2003 (to be presented).
大域的滑らかさを重視した補間曲面生成法
(共同研究者 室谷浩平)
空間に与えられた点群を通過する大域的に滑らかな曲面の表現法を
開発中である．曲率の２重和を全域で最小にする方針をとっているため，
不要なうねりなどの発生を防ぐことができる．ただし，局所的に形を
決めるわけではないので，従来の方法より大規模な連立方程式を
解かなければならない．
発表論文
-
Kohei MUROTANI and Kokichi SUGIHARA:
G1 surface interpolation using Gregory patches over irregular
meshes.
Proceedings of NICOGRAPH International 2002, Tokyo,
May 30, 2002, pp.97-102.
-
Kohei MUROTANI and Kokichi SUGIHARA:
G1 surface interpolation for irregularly located data.
Proceedings of Geometric Modeling and Processing -
Theory and Applications, 2002, Wako, pp.187-196.
-
Kohei MUROTANI and Kokichi SUGIHARA:
Globally smooth interpolation using Gregory patches over
irregular meshes.
International Journal of Shape Modeling (to appear).
結晶 ボロノイ図の近似算法とその応用 (共同研究者 小林景)
空間に与えられた点群を通過する大域的に滑らかな曲面の表現法を
開発中である．曲率の２重和を全域で最小にする方針をとっているため，
不要なうねりなどの発生を防ぐことができる．ただし，局所的に形を
決めるわけではないので，従来の方法より大規模な連立方程式を
解かなければならない．
発表論文
-
Kei KOBAYASHI and Kokichi SUGIHARA:
Crystal Voronoi diagram and its applications.
Furture Generation Computer System, Vol.18 (2002),
pp.681-692.
多面体メッシュのための透し埋込み法 (共同研究者 室谷浩平)
3次元多面体の表面を表すメッシュデータに透かしを安定に埋め込む
方法を研究している．この方法は，メッシュの頂点列の自己相関に
対するスペクトル分解を利用するものである．この方法では，透かしを
埋め込むための乱数表の任意性を，数値的安定化を図るために利用する
ことができ，その結果，合同変換などの多面体の基本操作に対して
ロバスト性をもっている．
発表論文
-
Kohei MUROTANI and Kokichi SUGIHARA:
Watermarking 3d polygonal meshes using the singular spectrum
analysis. 10th IMA Conference on Mathematics of Surfaces,
Leeds, September 15-17, 2003 (to be presented).
杉原厚吉のホームページへ