三角形分割
ドロネー網
グレブナによる分割
ト―リックイデアル
正則三角形分割
計算可能
グレブナ基底のリデュースは一意
課題
物理的な面に矛盾する分割の発生
母点から生成される網構造が直感的に明らかでない
対話的な更新の必要
パッチ
分割後が規則的
ボロノイ図，ドロネー網との差異
幾何アルゴリズム
ロボティクス
注意を要する研究テーマ
凸多面体間の最短距離を求める
多面体間の干渉チェック
低自由度ロボットの動作計画
計算幾何学
課題[1]
文献
[1]杉原，"計算幾何学的手法と画像解析-ボロノイ図の応用を中心として-"，1989
[2]Winfried Bruns, Joseph Gubeladze，"Polytopes, Rings, and K-Theory"，2009
(Chapter 7) Groebner bases, triangulations, and Koszul algebras
[3] 今井浩，今井桂子，"3角形分割と凸多面体"，1996
[4] Patricia Hersh，"Chain decomposition and the flag f-vector"，2002
数値誤差が原因となって現実にはうまく動作しない
補間；計測データが規則的に並ばない場合
補間；三角網のなかで，細長い三角形が現れにくいものが望ましい
どの点とどの点が隣かの判定
密度の異なる領域の境界付近で両者の中間の密度が計算値として現れ，分割が正しく行われないことがある
点同士の関係をより構造的に把握して解析する方法がほしい
ユークリッド距離に基づいた骨格線を効率よく抽出する手法がない？
画像解析への応用[1]
補間のための三角形分割
"隣り"の検出とその利用
粒状模様の解析
骨格線の抽出とその利用
安定手法の研究は進められている[1]
正則三角形分割(regular triangulation)
2,3次元で三角分割可能
三角形分割（基礎）
2次元：凸包を三角形に分割
3次元：単体（四面体）に分割
三角形分割（応用）
CG
有限要素解析
内挿でのメッシュ生成
未解決問題(1)
一般の点集合の三角形分割の個数を多項式時間で数えることができるかどうか
動的計画法より，多角形内部の三角形分割の数を数えることは多項式時間で行える(1)
ドロネー三角形分割(Delaunay)
すべての可能な三角形分割の中で，最小の内角が最大であるという意味で最適な三角形分割である(2)
各三角形の外接円が他の点を内部に含まない三角形分割として特徴づけられる．(1)
最小全域木
(ユークリッド)最小全域木は，点集合に対するデローネイ三角形分割の部分グラフである．(2)
点集合Sに対する最小全域木とは，すべての点を連結する木の中で辺長の総和が最小のものである(2)
(応用)経路の探索
基準(1)
- (最小角最大)
- (最大角最小)
- (重み最小)
- (最大最小包含円最小)
- (最大アスペクト比最小)
三角形分割での全角度の最小のもの(最小角)を最大にする
三角形分割での全角度の最大のもの(最大角)を最小にする
三角形分割の辺長の総和を最小にする
三角形分割の各三角形の最小包含円(鈍角三角形の場合，鈍角の対辺を直径にする円)のうち最大のものを最小にする
三角形分割の各三角形のアスペクト比(三角形の外接円半径と内接円半径の比)の最大のものを最小にする
最小角最大を例にすると，すべての角度を小さい順に並べたベクトルについて，ドロネー三角形分割は辞書式順序で最大なベクトルを与える(1)
高次元の三角形分割の構造は一般に難しい
3次元で，非凸の多角形の内部を新しい点を導入することなく四面体に分割することができるかどうかという問題は，NP困難
一般化された高次元対角変形により任意の三角形分割間で変換できるかどうかもわかっていない
[2]
点集合Sに対して新たなもう1次元方向を考え，その各方向に高さを与え，その分だけ新しい次元方向に持ち上げた点集合の凸包の下側境界を元の空間に正射影することにより得られるものである．(1)
もし，その凸包の下側境界にすべての持ち上げられた点がのっており，さらにそれが一般の位置にあれば，正射影されたものはまさしくこれまでの定義の三角形分割である．
正則三角形分割では与えられた点で三角形分割の頂点として使われないものもある
2次元でも正則でない三角形分割は存在する
ドロネー三角形分割は正則である(1)
高次元の場合も任意の2つの正則三角形分割は一般化対角変形で変換することができ，2次元の三角形分割にも通じるよい性質をもっている．(1)
凸多面体と密接な関係を持った概念で，数学・組み合わせ論で色々な展開が図られている(1)
ボロノイ図
- 平面を与えられた点のどれに近いかによって分割したもの(3)
- 平面上の多数の点が与えられたとき，平面をどの点に最も近いかという関係だけで分割したのも(2)
地理的最適化問題
従来(3)
思考実験的な側面が強い
配置問題としての意味づけは現実的でない場合も多い
応用
(3)
管区割問題
競争立地
ex: ラゲールボロノイ図，ラゲール距離の意味で近いかどうか
ex: 救急車の担当地区の決定問題 (最短距離)
(2)
商圏の定義：社会地理学への応用
植物の勢力圏図
ロボティックスへの応用（最も安全な経路の発見）
メモ
[1] 2002 Chain decomposition and the flag f-vector
厳密な定義[3]
任意の高さにして（持ち上げて）得られる3角形分割[3]
Delaunay3角形分割では持ち上げる量が点の座標により決まっていた
内点で持ち上げ過ぎた点は使われない3角形分割が出てくる
厳密には[3]
[3]
ブーリアングレブナ
消去理論
[4]
記号限定消去？
任意の物体に対して三角形分割し，クエリとして扱う三角形が含まれるかどうかを調べ，マッチングすることはできるか？
3D(メッシュ，表現)
圧縮(compression)
如何に効率よくメッシュを作るか，補間するか
Youyou Wang, Guilherme N. DeSouza,"A New 3D Representation and Compression Algorithm for Non-Rigid Moving Objects using Affine-Octree" ,2009
グラフ理論
ホモロジー，位相
Graph Signal
2000 Efficient polygonal decomposition into singular and regular regions via Voronoi diagrams
比較的最近 2013~
Graph signal decomposition for multi-scale detail manipulation
ホモロジー理論
複数要素で分解可能？
マッチング可能？