本
数理工学ライブラリー (室田一雄さん、杉原正顕さん[編])
計算幾何学 by 杉原厚吉さん
2013年6月初版の本である。
Delaunay diagramと、そのdual graph(双対図形)であるVoronoi diagramについて詳しい。
興味を持ったキーワードだけ整理する
(ページの位置 t:top, m:middle, b:bottom)
- pi 有限、離散
- p3t シェーモス (M.I. Shamos)
- 学位論文 「computational geometry」
- p6m Xは凸 (convex)
- p7t 凸包 (convex hull)
- p7m CH(X)
- (補足) converx hullの略語CHなのだろう
- p7b 述語 (predicate)
- p8m 反時計回りのxy座標系
- p8b
F(p1, p2, p3)=0 - p10t X\Y
- Yを除外したX
- p10b A<-B
- p11t for A do B
- p11m [コメント: A]
- p13m T(n)秒
- p14t 空間複雑度
- p14m k
- Xの凸包の境界をなす有向辺の数
- p15m 計算量、減らす
- p15m 内部通過(見えない)、そうでない（見える)
- p18m 効果がない場合
- すべての点が境界付近に集まる場合
- p20t 余弦定理
- p20b 計算量 O(kn)
- p22t 退化判定
- p22t 計算誤差
- p25t 欧米の教科書
- XXXについてほとんど議論されていない
- p25m 安定動作
- 設計方針２つ
- p25b 厳密計算法 (整数帰着法)
- p25b 記号摂動
- p26t 組合せ位相的構造の整合性を持つ
- p26b ハンドブック
- p27t 学術雑誌
- p27m 国際会議
- p28t 超ロバスト
- p28m 記号摂動
- 退化を自動的に解消する
- p29t 厳密計算法
- p29m 正しい座標であると見なす
- p29b アダマールの不等式
- p30t 2k+2ビット
- p30b 整数帰着法
- p31m 退化処理の困難を統一的に回避
- p31m 数値摂動
- p31b 記号 $\epsilon$ (epsilon)
- p32t Z
- 整数全体の集合
- p32b fi not equal 0
- p32m fの符号
- fi epsilon^i だけで決まる
- p32b 反射律
- p32b 反対称律
- p32b 推移律
- p32b 順序 order
- p33t 全順序集合
- totally ordered set
- p33b 多項式の代数的構造
- p34t 結合的 (associative)
- p34t 可換 (commutative)
- p34t 単位元 (unit element)
- p34m 逆元 (inverse element)
- p34m 可換群 (commutative group)
- p34m 半群 (semi group)
- p34m 分配律 (law of distribution)
- p34m 環 (ring)
- p34m 順序環 (ordered ring)
- p35t 入力データ + epsilon多項式
- p35t Fの符号
- p35t leftturnの値
- p35m 式(2.9)の意味
- p35m 式(2.10)の意味
- p36t Fの符号, 述語, 意味
- p36t 式(2.12), leftturnの値, 摂動を加える前のF
- p37m p_iのx座標の摂動だけでは退化解消できない
- p38t 式(2.12) 符号判定
- p38b 記号摂動 (symbolic perturbation)
- p39t すべての退化に対応できる
- p39m 計算時間の増加
- p39m 信頼できないときのみ整数帰着法へ
- p39b mビット
- 有効桁数
- p39b m-1ビット
- 信頼できる
- p40t m-3ビット
- 丸め誤差
- p40t (2.14)
- 符号は信頼できる
- p40m 浮動小数点加速 (float-point accelleration )
- 補足: スペルミス。正しくは(float-point acceleration)
- p40b 有限の精度で厳密に判定
- p41t Khachianの楕円体法
- 多項式で解ける
- p41m ソリッドモデラ設計法
- 杉原・伊里
- 補足: 数値計算の本でお世話になっている伊里正夫さん
- 原理を計算幾何の問題にはじめて適用
- 杉原・伊里
- p41m 記号摂動、線形計画法
- p41m Blandの方法
- Edelsbrunner、Yap
- p41b ロバストな幾何アルゴリズムの重要性
- p42t 2線分の交差判定
- p42b l1とl2が交差するためには
- p42b G1 式(3.1)
- p42b G2 式(3.2)
- p43t ...のときにはl1とl2は交差する
- p43m 3点が一直線上に並ぶ場合は
- p43m G1とG2の少なくとも一方が非負の場合には
- p43b G1=G2=0の場合
- p44t 退化をなくすことはできる
- p44m 集合L
- 平面上のn本の線分
- p44b 交差検出問題
- ...ときなどに生じる
- p45t 平面走査法 (plane-sweep method)
- p45t 1本の垂直な直線
- 左から右へ走査
- p45t 走査線s
- p45t 記憶領域A, B
- p46t 平面走査法のアルゴリズム
- p48t アルゴリズムの時間複雑度
- p48m $l$を挿入すべきB上の場所
- p48b 必要な比較の回数 k
- p48b k = O(logn)
- p49t O(n)
- p49t O(nlogn)
- p49t 線分の交点列挙
- p49m 変更点は次の2つ
- p49b 検出された交点位置も加える
- p50t アルゴリズム3.2 交点列挙
- p51m ヒープ
- 特殊な構造の2進木
- p51m 最小の項目を取り出す
- O(logn)
- p51b 時間複雑度 O(n^2 logn)
- p51b 交点の数がもっと少ないときには、効率のよいアルゴリズム
- p52m 平面走査法
- p52m 背景空間と共に対象をとらえるという考え方
- p52b 時間複雑度を保ったまま空間複雑度の最適性も達成
- p52b 平面走査法、いろいろな幾何問題を解く
- 最近点を求めるShamos and Hoeyの方法 120)
- ボロノイ図を求める Fourtuneの方法 45)
- 一般化ボロノイ図を求める Dehne and Kleinの方法 30)
- ドロネー図を求めるZalikの方法 156)
- 図形の被覆問題に対するFranzblau の方法 48)
- 円の包含関係を求めるKim et al. の方法 82)
- 円ボロノイ図を求めるJin et al. の方法 74)
- p53m ボロノイ図、これは...
- p53m 双対図形はドロネー図
- 補足: Delaunay diagram
- p53b 集合S、n個
- p53b ボロノイ領域 (Voronoi region)
- p54t ボロノイ辺 (Voronoi edge)
- p54t ボロノイ点 (Voronoi point)
- p54t 生成元 (generator)
- p54t 母点 (generating point)
- p54m 次の性質が成り立つ
- p55t 退化ボロノイ点 (degenerate Voronoi point)
- p55m ボロノイ片は線分または半直線
- p55m 半直線となる場合は次のように...
- p55m q
- Sからどんどん遠ざかっていく点
- p56m n, n_e, n_v, n1, n2
- p56m ボロノイ辺やボロノイ点の数を見つけやすくするには
- p56m 閉じたボロノイ図 (closed Voronoi diagram)
- p56m 頂点 (vertex)
- p56m 辺 (edge)
- p57t V - E + F = 2
- p57t 閉じたボロノイ図
- V=
- E=
- p57b すべての面の角数の合計
- p57b 1つの面当りの平均の角数
- p58t 母点数をnとすると
- ボロノイ辺の数もボロノイ点の数もO(n)
- p58b z軸負方向へのびた円錐面
- p59t これらの円錐はz軸負の方向へ...
- p59t 2つの円錐の側面の光線をxy平面へ垂直に投影してできる線は...
- p59t ボロノイ図を近似的に計算する次の方法
- p59m もっと簡単な計算に帰着できる
- p60m 平面のアレンジメントに対して隠面消去を行うだけで...
- p60m 連結であるべきボロノイ領域が、2個以上の連結成分に...
- p60b 1つの画素が他から離れた飛び地
- p61t ...を数えればよいから
- p61t 3個の母点の作るボロノイ点の計算法
- p61m G(pi, pj, pk, p) = 0
- (4.13)
- p62m G(pi, pj, pk, p)=0が表す円の中心
- p63b 元のxy座標系へ戻すと
- (4.27)
- p64t (4.19) 桁落ち
- (4.27) 心配が少ない
- p64m 実用性を重視する
- p64m 逐次添加構成法
- p65t 2つに分けた領域のうち新しい母点に近い方を集める
- p65t 古い母点より新しい母点に近いものを見つける方法
- p65m 性質4.9
- ...とは等価である
- p65b 木(すなわちサイクルをもたない連結なグラフ)
- p66m 取り除くべきすべてのボロノイ点を芋づる式に見つける
- p66m 取り除くべきボロノイ点の数は...
- p66m 平均的に定数時間で除くべきボロノイ点の集合を見つける
- p66b もっと効率よく見つける「バケット」という考え方
- p67t 4分割を繰り返す回数の目安
- p67t バケット (bucket)
- 最終的に得られる最も小さい正方形
- p67t この4分割の手順を4分木で表す
- p67m 逐次添加法の途中で母点piが追加されたとしよう
- p68m 新しい母点に非常に近いものであることが期待できる
- p68m この方法で..にすばやくたどり着くことができ,...
- p68m 平均的にO(n)の時間で構成できる
- p68b 有限の精度の計算、安定に動作するロバスト性
- p69t アダマールの不等式
- p69m ボロノイ図を構成するための述語incircleは...
- p69m この困難を回避し、...するロバストな計算方法を構成
- p69b 結果を信じることができないので
- p70t ボロノイ図の更新作業の骨子
- アルゴリズム4.1
- p70m ボロノイ図の更新作業は...しながら実行される
- p70b 位相優先法 (topology oriented method)
- p71m 判定を誤っているにもかかわらず、計算結果が得られていること
- p71m ...に描くと、領域の数は母点の数と一致する
- p71b 現実に近い状況での位相優先法の振舞いを図4-11に...
- p71b 位相優先法ではどれほど過酷な数値誤差が発生しても...
- p72m ドロネー図 (Delaunay diagram)
- p73t ドロネー辺 (Delaunay edge)
- p73t ドロネー多角形 (Delaunay polygon)
- p73t ドロネー三角分割 (Delaunay triangulation)
- p73m ドロネー図の母点 (generating point)
- p73m ドロネー図はボロノイ図の双対図形
- (補足) dual graph
- p73m 空円 (empty circle)
- Sの要素を内部に含まない
- p73b ドロネー辺の数は3n-3以下
- p73b ドロネー多角形の数は2n-2以下
- p73b Sの張木（ちょうぎ) (spanning tree)
- p74t 最小張木 (minimum spanning tree)
- p74t
|S|=nのとき、Sの張木はn-1本の辺をもつ - p74m Sのドロネー図とSの最小張木の間には、次の関係がある
- 性質 4.14
- p74b 最小張木Tは、T1とT2をeでつなぐ構造
- p75t ...のものは、Gの最小張木と呼ばれる
- p75t アルゴリズム4.2 (グラフの最小張木)
- p75m Tを辺集合とするグラフは、Vの張木である。なぜなら...
- p76t アルゴリズム 4.2の時間複雑度
- p76m 辺e_iが異なる連結成分をつなぐかどうかを調べるためには...
- p76m n=O(m)だからアルゴリズム4.2の時間複雑度はO(mlogm)
- p76m 連結成分番号の直接書き換えが最も多く生じるのは...
- p76b アルゴリズムを直接適用するとO(n2logn)の計算時間がかかる
- p76b 性質4.14より、Sの最小張木はSのドロネー図の部分グラフの中で探せばよい
- p77t ボロノイ図・ドロネー図の複雑さがO(n)しかない...
- p77t 2次元のドロネー図と3次元の凸包の間の1つの関係
- p77t 3次元空間の点p_i*を...
- p77m SからS*を作る操作は...
- p77m 性質4.15 ...は、Sに対するドロネー図と一致する
- p78t 行列式の値が0となり、...ことがわかる
- p78m ...の符号によって、平面のどちら側にあるかがわかる
- p78m xyz座標は右手系
- p78m 反時計回りに円周上に並んでいる
- p79t 式(4.32)と式(4.12)
- p79m ...が等価である
- p79m 性質4.15, ドロネー図を作る, アルゴリズムの方針
- p79m n個の点の3次元凸包, 計算時間, 111)
- p79m 2次元ドロネー図が3次元凸包を介して作れることを最初に示したのは
- Brown 22)
- p79b 三角形分割Tの内角昇順列 (increasing list of inner angles)
- p80m 辞書式順序 (lexicographic order)
- p80m ...が辞書式順序が小さいといい
- p80m 性質4.16 (最小内角最大性)
- p80b ドロネー三角形分割が役立つ根拠を与える
- p81m ...した方が、三角形の内角の最小値は大きくなる
- p81m 局所ドロネー性 (locally Delaunay property)
- p81b ...する操作を局所ドロネー化という
- p81b
T*- 最終的に得られる三角形分割
- p82m 空間の3点を通る平面に対して第4点が上か下かを表す
- p82m 三角形の外接円が第4点を含むか否かを表す
- p82m ...は局所ドロネー性を満たさないことがわかる
- p82m この性質は、観測データの補間や三角形メッシュの生成などに応用できる
- p83t Aの定義
- 平面上の凸で有界な領域
- p83t Sの定義
- Aに属すn個の母点の集合
- p83t 制限ボロノイ領域 (restricted Voronoi region)
- p83m 重心ボロノイ図 (barycentric Voronoi diagram)
- p83m ...の利便性を最大化する施設配置計画
- p85m 性質4.17 重心ボロノイ図
- p85m ウォード法 (Word Method)
- p85m アルゴリズム 4.3 重心ボロノイ図のためのウォード法
- p85b 図4.18 アルゴリズムの振舞いの例
- p86m ...という制限のもとで
- p86m さらによいメッシュを作ることができる可能性
- p86b すべての重心ボロノイ図が...わけではない
- p86b 小さなゆらぎが加わった場合のボロノイ図の安定性
- p87m ほぼ確実に安定な重心ボロノイ図
- p87b ...ので心配はいらない
- p88t 104, 106, 10, 12, 135, 47
- p88m O(nlogn)の算法 55, 91, 111, 45, 22
- p88m O(n)の平均計算時間を達成する 102
- p88m ボロノイ図・ドロネー図の応用 70, 71, 105, 18, 50, 58, 122
- p88m ロバストなものにした位相優先アルゴリズム 143, 144
- p89t この領域は、...とみなすことができる
- p89m p_iのボロノイ領域は(5.1)で定義された
- p89m $d(p, p_i)$
- ...のユークリッド距離
- p89m S: 生成元 (generator)
- p89m U: 背景空間 (underlying space)
- p89m d: 距離 (distance)
- p89b 一般化ボロノイ図 (generalized Voronoi diagram)
- p89b ...したいときには、...母点という言葉も併用する
- p90t (5.2)を距離dに関する**二等分曲線 (bisector)**という
- p90t 一般には、二等分曲線は直線ではなく曲線となり
- p90m ...によってボロノイ図のバリエーションを作ることができる
- p90m ...は、必ずしも距離公理を満たすとは限らない
- 補足: 距離の公理
- p91t 新しいボロノイ図のバリエーションを作るためには...
- p91m マンハッタン距離 (Manhattan distance)
- p91m これは...に相当する
- p91m マンハッタン距離ボロノイ図 (Manhattan-distance Voronoi diagram)
- p91b この距離に対する**円(circle)**と呼ぶことにしよう
- p92m マンハッタン距離ボロノイ図は...とみなすことができる
- p92b (5.6)を2点の**Lp距離 (Lp-distance)**という
- p92b (5.7)を2点の**L∞距離 (L∞-distance)**という
- p92b Lp距離ボロノイ図 (Lp-distance Voronoi diagram)
- p93m L∞距離は、...と解釈できる
- p93b L∞距離ボロノイ図を作りたかったら...
- p94t 楕円距離ボロノイ図 (elliptic-distance Voronoi diagram)
- p94t 楕円距離 (elliptic distance)
- p94t アフィン変換によって...の定義された平面へ移すことができる
- p94m この性質を利用して...に帰着できる
- p94m 性質5.3
- アフィン変換、逆アフィン変換
- p95t ユークリッド距離の逆数
- p95m 最遠点ボロノイ図 (farthest-point Voronoi diagram)
- p95m 非空なボロノイ領域
- p96t Sの包含円 (enclosing circle)
- p96m 最遠点ドロネー図 (farthest-point Delaunay diagram)
- p96m 最遠点ドロネー三角分割 (farthest-point Delaunay triangulation)
- p97t ...すれば最遠点ドロネー図が得られる
- p97m ...によって、ドロネー図と最遠点ドロネー図の両方を同時に作ることができる
- p97m (5.9) ラゲール距離 (Laguerre distance)
- p98m (5.11) この式から...であることがわかる
- p98m ボロノイ領域が凸多角形であるから...である
- p98b ラゲールドロネー図 (Laguerre Delaunay diagram)
- p98b 円 (p_i, w_i)
- p99t 両方の円までのラゲール距離はどちらも...
- p99t 性質5.6を利用すると...を見通しよく計算することができる
- p99t アルゴリズム5.1
- 円盤の和集合の面積と周長
- p100t (5.12)
- 加重距離 (weighted distance)
- p100t 乗法的重み (multiplicative weight)
- p100t 加重ボロノイ図 (weighted Voronoi diagram)
- p100m 加法的加重距離 (additively weighted distance)
- p101t 乗法的加重距離に関する二等分曲線は...
- p101m アポロニウスの円 (Apollonius circle)
- p101b 障害物回避距離 (collision-avoidance distance)
- 補足: 日本語に合わせるならobstacle-avoidance distance
- 補足: 英語に合わせるなら「衝突回避距離」
- p101b 障害物回避距離ボロノイ図 (collision-avoidance Voronoi diagram)
- p102m 距離を計算, 微分方程式, アイコナル方程式
- p102m 距離の一般化による...
- p102m ...に対して適用できる１つの汎用的な算法
- p103t 円錐, 四角錐, 四角錐
- p103t それぞれに応じた形の錐体となる
- p103m したがって、...表せばボロノイ図の近似図形となる
- p103b 生成元の一般化
- p104m 一般図形ボロノイ図 (general-figure Voronoi diagram)
- p104m 円ボロノイ図
- 線ボロノイ図
- 多角形ボロノイ図
- p104b 一般図形ボロノイ図は...と解釈することができる
- p104b 一般図形ボロノイ図を構成する汎用の近似算法
- p105m 母点リストLのボロノイ領域
- p105m 順序つきk階ボロノイ図 (ordered order-k Voronoi diagram)
- p105m 順序つきk階ボロノイ図は...である
- p106t R(S; T)は...を集めてできる領域
- p106t (順序なし)k階ボロノイ図 ((unordered) order-k Voronoi diagram)
- p106m 順序なしk階ボロノイ図は....を除いて得られる
- p106b ...が順序つきk階ボロノイ図に対応し
- ...が順序なしk階ボロノイ図に対応する
- p107t 3次元ボロノイ図 (three-dimensional Voronoi diagram)
- p107m ...をなす多角形を**ボロノイ面 (Voronoi face)**という
- p107m 3次元ボロノイ図, 多結晶構造の数理モデル
- p107b 3次元ドロネー図 (three-dimensional Delaunay diagram)
- p108t 3次元では...O(n2)の複雑さ...
- p108m ...=O(n2) (5.22)
- p108m ...に相当する性質は、3次元ドロネー図では必ずしも満たされない
- p108b 次元は2次元のままで、平面を曲面に置き換えることによって...
- p108b 測地距離(geodesic distance)
- p109m 球面ボロノイ領域 (spherical Voronoi region)
- p109m 球面ボロノイ図 (spherical Voronoi diagram)
- p109b 大円弧で囲まれた球面多角形
- p110b この性質は、球面ボロノイ図を...するための算法として利用できる
- p110b 5.4.3 流れの中のボロノイ図
- p112m セティアン(Sethian)の高速前進法 118)
- p112b 生成元、距離、背景空間の3つ
- p112b 文献
- 色々
- p113m ...の間には、密接な関係がある
- p113b ...によって、...などが統一的に構成できる
- p113b この一連の性質はEdelsbrunner and Seidel 38)に詳しい
- p114t 有限要素法
- 補足: Finite element Method (FEM)
- p114m ...の精度が悪くなるからである
- p114b "ふっくら"とした三角形という要請
- p114b ...ができるだけ大きい方がよいという指針
- p115t ...は、内角上昇列が辞書式順序で最大である
- p115t ...と定義すると、最適な三角形分割は...を作ることによって得られる
- p115m ドロネー三角形分割は、最小内角最大性が保証されている
- p115b よりよいメッシュが得られるように母点を動かす代表的方法
- p116t ラプラス平滑化 (Laplacian smoothing)
- p116m 母点の移動
- 並列的な方法
- 逐次的な方法
- p116m ...という意味で後者の方が性能がよいと期待できる
- p116b ラプラス平滑化が...に対して、...ウォード法は...
- p117m 境界を横切る三角形
- p117b ...を優先し、...を作らなければならない
- p117b その方法について考える
- p118t Cを制約(constraint)とする...
- p118b 制約つきドロネー三角形分割 (constrained Delaunay triangulation)
- p118b 母点集合S
- p118b 制約辺集合C
- p119t 共形ドロネー三角形分割 (conformal Delaunay triangulation)
- p119t ...を実現できる可能性
- そのために役立つのが次の性質
- p119b したがって、空円に近づくと期待できる
- p119b アルゴリズム6.1 共形ドロネー三角形分割を目指した母点の追加
- p120m 終了しない危険性
- p120m 危険性, 2つのパターン
- p121t アルゴリズム6.1は,...が満たされるとき終了する
- p121m ...が終了するための十分条件であるが、必要条件ではない
- p121m ...してみるのも無駄ではない
- p121m ...母点を追加するためのもう一つの方針
- p122m S*, Sの垂直持ち上げ (vertical lifting)
- p122m S*の下側包絡面 (lower envelope)
- p122b T, 正則三角形分割 (regular triangulation)
- p122b 図6.7, 正則ではない三角形の分割
- p123m この二項関係が"すくみ"を生じないとき
- p123m 視線単調整 (ray monotonicity)
- p123m ...の三角形分割は, 視線単調性をもたない
- p123b 三すくみ
- t1 <= t2 <= t3 <= t1
- p124m D, Sを母点集合とする正則三角形分割
- p128t 四面体メッシュ (tetrahedral mesh)
- p128t 四面体メッシュは...に使われる代表的なメッシュ
- p128m ふっくらとしていない四面体
- p128b この四面体. スリーバー(sliver)
- 補足: スペルからすると発音は「スリバー」だろう
- 「スリーバー」という用語として確立してしまっているのだろうか
- p129t ドロネー四面体分割では...を回避することができず
- p129t ...のよいアルゴリズムはほとんど知られていない
- p129t ...が大きな課題の一つ
- p129m 重要な未解決問題
- p129b 単体メッシュ
- p129b 構造メッシュ
- p129b できるだけよりメッシュを作るための点の配置法
- このためには...が有用である
- p130t 制約を満たすために使われる主な方針
- p131m 頂点(vertex)
- p131m 接点(node)
- p131m 弧(arc)
- p131m 接続辺(link)
- p131b ...の端点(terminal vertex)
- p131b ...の次数(degree)
- 補足: spherical harmonics > order, degree, mode
- p131b ...をつなぐ経路(path)
- p132t 経路の長さ(length)
- p132t **連結(connected)**である
- p132t 互いに**隣り(adjacent)**である
- p132t T(mu)
- ...と隣り合うすべての頂点の集合
- p132m アルゴリズム7.1 (最短経路)
- p133t このアルゴリズムの各ステップの直観的な意味
- p133m 性質7.1 ...への最短経路の長さを表す
- p134m 最短経路自体は...によって得られる
- p134m $d(\nu)$の値をキーとするヒープ構造
- p134m アルゴリズム7.1の時間複雑度
- p134b ...という操作は、1本の辺当り2回
- p134b O(n) + nO(logn) + mO(logn) = O(nlogn) ... (7.4)
- p135m ネットワークボロノイ図 (network Voronoi diagram)
- p135m ...を考える最に有用である
- p136t このような状況は...する場合に発生する
- p136t tree-edge(e)は...なら値1をとり,そうでなければ値0をとる
- p136b ...に対して、$g(\nu)$と$g(e)$が最も近い母点を表し
- p137b どの多角形にも属さない2点 $\nu_s$, $\nu_t$
- p137b 障害回避経路 (collision-avoidance path)
- 補足: Which path you choose?
- p137b 障害回避最短経路 (collision-avoidance shortest path)
- p138t このひも...ゆっくり引っ張ったとしよう
- p138m ひも...張った状態...局所的な最短経路
- 補足: Riemann Conjecture
- p138b グラフ(V,E)を**可視グラフ (visibility graph)**という
- p139t 図7.4 可視グラフ
- p139m このアルゴリズムの時間複雑度
- p139b Xの境界を$\partial X$で表す
- 補足: round X
- p139b S(X), **Xの骨格線 (skeleton)
- p140m pを中心とする半径rの円盤を**disk(p, r)**で表す
- p140m $\partial X$と2個以上の点を共有する円が存在する
- p140m ...と...から元の図形Xを復元できる
- p140b S(X)はXの概形を表すとみなすことができる
- p141t ひげのような枝
- p141t ひげを除く方法
- p141m 曲線$\partial X$に沿って測ったpとqの距離 $d\partial X (p,q)$
- p141m 経路は2つ, 短い方の長さ
- p142t ST(X), 骨格線の点のうち重要度T以上の点のみ
- p142t C, 図形X内の閉曲線
- p142m ホモトピー同値 (homotopically equivalent)
- p142m ホモトピー同値であるときC1 ～ C2と書く
- p143t C(X), Xに含まれるすべての閉曲線の集合
- p143t ホモトピー同値という...は、C(X)の中の同値関係
- p143m ホモトピー同値であるとは...ことを表す
- p145t SS(X)
- p145t 直線的骨格線 (straight skeleton)
- p145m 直線的ボロノイ図 (straight line Voronoi diagram)
- p145m 直線的骨格線は...に応用できる
- p145b 国土の面積を測ること
- p146m ...れば、面積の上限が得られる
- p146m 海岸線の長さを計ること
- p146m 面積の場合と異なり、上限は得られない
- p147t この折れ線が...の近似値とみなす
- p147m ...は一定の値に収束するであろうか
- p147b フラクタル(fractal)図形
- p147b 代表例, コッホ曲線 (Koch curve)
- p148t 長さは4/3倍される
- p148m 幾何的フラクタル図形 (geometric fractal curve)
- p148m 海岸線の場合は...とは違って
- p148m 統計的フラクタル図形 (statistic fractal figure)
- p149m Xの次元
- p149m ...のとき...Xのフラクタル次元 (fractal dimension)
- p149m 海岸線に対しても、同じように次元を計算...
- p149m 全体の3分の1に縮小したもの4個で...
- p150t 川の形...葉の形...稲妻の形
- p150m ...る問題を考える
- p150m 問題を定式化しよう
- p150m ...場合などに現れる
- p150m これを**空送り (pen-up movement)**と呼ぶ
- p150b 空送りをまったくしない... ひと筆描き (single-stroke drawing)
- p150b vの次数, deg(v)
- p151m 任意の頂点v_sから出発して
- p151m vに接続する辺の集合をT(v)とする
- p151m 奇数次数,偶数次数
- p151m 最後はv_tで終わる
- p151b x o yという記号は
- p152t pass(e) = 0は...
- p153t グラフ(V,E)のすべての頂点の時数が偶数のときには...
- p153t アルゴリズム7.4の時間複雑度
- p153m ...たから、平面グラフである
- p153m 奇数次数頂点の集合 V_1
- p153m 空送りする時間 c(v,v')
- p153b ...をV_1の**マッチング(matchinig)**という
- p153b 完全マッチング (complete matching)
- p154t 頂点の次数はすべて偶数
- p154m 最小完全マッチング問題 (minimum complete matching problem)
- p154m 厳密解を得ることが困難な問題
- p154m 近似解を得る簡便な方法
- p154m ...の小正方形、バケット(bucket)
- p155t アルゴリズム7.5 最小完全マッチングの近似解
- p155m このアルゴリズムの基本は
- p155b これによって...であるという状態を保ちながら...
- p155b ...を利用する情報処理技術、バケット法 (bucket method)
- p156t 雨量計のおかれていない場所、雨量を推定
- p156m ...された点の集合, S={p1, p2, ..., pn}
- p156m 観測点 (data point)
- p156m z(p_i), p_iでの観測値
- p156m pに近い観測点の集合 S_p ⊆S
- p157m pの回りを囲むものを選ぶこと
- p157m 観測点のドロネー三角形分割
- p157m 重みw(q)
- 単調減少関数
- or
- 重心座標値
- p157m いつも3個の観測データしか使えない
- p158t T_i(p), p_iのpへの寄与領域 (contributing area)
- p158t Area(x)、領域Xの面積
- p158t S_p、pの自然近傍 (natural neighbor)
- p159t q_1, q_2, ..., q_M, 寄与領域がx軸と交わるもの
- p160t y軸に平行に移動してもそのまま成り立つ
- p160m 90度回転させて同じ議論を行えば
- p160m 隣り合う母点のアフィン結合
- p160m (7.22) シブソンの自然近傍補間 (natural neighbor interpolation)
- p160m C^1 連続である
- p161t 中心軸が不安定となるという欠点を克服
- p161t Aichholzer and Aurenhammer 2)
- p162m 面(face), 稜線(edge), 頂点(vertex)
- p162m 互いに合同か否か
- p162m 頂点・稜線グラフ (vertex-edge graph)
- p162b 2つのグラフは同型 (isomorphic)
- p162b 同型問題がやさしくなる場合がある
- p162b Gは3連結 (3-connected)
- p162b 平面グラフ (planar graph)
- p163t 3連結平面グラフの同型判定は効率がよくできることがわかっている
- p163t ...が...に対してやさしくなるのは
- p163t によって、同型か否かを効率よく判定
- p163t ...とみなすことができる
- p163m 表と裏の区別できる面に
- p163m 多面体の合同判定を効率よくするアルゴリズム
- p163m 等長 (isometric)
- p163b 向きを保存する (orientation-preserving)
- p163b 合同変換 (congruent transformation)
- p163b 面・稜線 (face-edge graph)
- FG(p)
- 補足: FEG(p)の方が良い (Face-Edge Graph)
- p164t
B(x; r) {y | y ∈ R^3, d(x,y) <= r } (8.2)- 半径rの球体
- p164m 単連結 (simply connected)
- p164m 非空で単連結であるという性質
- p164m 紙のような厚みのない立体は
- p165t 面に穴が開いていないことを意味
- p165t ...してfのすべての辺を列挙
- p165t **頂点・稜線グラフG(P) = (V(P), E(P))
- p165m 始点 (initial vertex)
- p165m 終点 (terminal vertex)
- p165m 逆向きの辺 $e^r = (v_2, v_1)$
- p165b ...したとき反時計回りに並ぶ順序を一意に定める
- p165b eの右側の面 $f_R(e)$
- 左 $f_L(e)$
- p166m ...のときe'を最右辺といい
- p166m eの長さ $l(e)$
- p166b この有向道を**基本道 (primary path)**という
- p166b したがってC_iは常に一意に確定する
- p167t pに対応する道 (corresponding path)
- p167t 識別不可能 (indistinguishable)
- p167b 等長変換
- p169t アルゴリズム8.1 多面体の合同判定
- p169m 手続き SUBDIVIDE
- p170t 入力値が等しいもの同士の同値類
- p170t ...からなる同値類があるか否かを調べ
- p170t 互いに識別不可能な辺の同値類へ細分
- p170m 順次分割、このとき現れる集合をブロックと呼ぶ
- p170b 辺eの隣の辺$gD^{-1}(e)$の集合MOVE
- p171t SUBDIVIDEでやっていることは
- p172m 調べられる辺ののべ総数はO(nlogn)
- p172b 厳密に同じかどうかではなくて、互いに似ている図形
- p173t その図形に最も近いものを作りたいという場面
- p173t ２次元図形、最も近くてタイリング可能な図形を見つける
- p173m タイリング芸術に革命、オランダの版画家 エッシャー
- p173m エッシャー化問題 (Escherization problem)
- p173m カプラン(Kaplan)とサレシン(Salesin)が最初に...
- p173b T、タイリング (tiling)
- p173b Tの要素、タイル (tile)
- p173b 単一タイルによるタイリング (monohedral tiling)
- p174t ...が存在するときTを**アイソヒドラルタイリング (isohedral tiling)**という
- p174m アイソヒドラルタイリングは17種類に分類される
- p174m ...の境界が共有する曲線、タイリング辺 (tiling edge)
- p174m ...の境界が共有する点、タイリング頂点 (tiling vertex)
- p174m 目標図形 (goal shape)
- p174m タイリング可能図形 (tilable shape)
- p175t アイソヒドラルタイリングのグラフ構造に着目した... IH1～IH93
- p175t 図8.3 ...を基本とみなす
- p175m このタイリング.. 5つのタイリング頂点、5つのタイリング辺
- p175m ...に反時計回りの向きと、記号a,b,c,d,eを与える
- 補足: 誤植？「...に反時計回りの向きに、記号a,b,c,d,eを与える」
- p176t IH31というパターンでタイリングできるという性質を保つため
- p176t タイル境界を表す折れ線の頂点の数 n=6k
- p176m ...から反時計回りにq1, q2, ...と通し番号をつける
- p176m タイリング辺aとbの組合せに着目
- p176m 右下の頂点q_kを中心にして時計回りに90度回転
- p176b 図8.5 タイリング可能性を保つための条件
- p177t cos90°、sin90° 回転行列 @ (8.9)
- p177b タイプIH31のタイリングができるためには...
- p177b (8.12) すべての未知数を並べてできるベクトル x
- p177b 線形で斎次(定数項を含まない)
- p177b (8.13) Ax=0
- p177b IH1からIH93、お暗示ような斎次の線形方程式
- p178t 未知の図形Qをできるだけ目標図形Wに近づけたい
- p178t 距離の２乗誤差を最小化することによって...
- p178m ...を求める問題は...問題に帰着できた
- p178m 正方行列A1、...をA2
- p178b $\overline{u_1}$, $\overline{u_2}$
- p179m ...に最も近いタイリング可能図形Qは
- p179m 93種の...に対して同様の計算
- p180m 8.3 投影図からの立体認識
- p180m 投影図D
- p181t 接続対 (incidence pair)
- p181t 立体を復元する問題
- p181t この座標の第3成分が0なのは...
- p181m $f_j^*$を含む平面 (8.25)
- p182t 線形な方程式
- p182t $A\omega = 0$ (8.29)
- p182t 相対的な遠近関係の制約
- p183t これらすべての不等式、(8.35)
- p183m 式(8.29),(8.35)が解をもつか否か
- p183m しかし、この方法は現実的ではない
- p184m ...ができる図であっても、式(8.29), (8.35)は解をもたず
- p184m (8.29)を次の近似式(8.36)に置き換える
- p184m さらに制約を追加しなければならない
- p185m 不可情報を与えられる場面では
- p185b ペンローズの三角形 (Penrose triangle)
- p185b 不可能物体 (impossible object)
- p186m 頂点位置にデジタル化の誤差が含まれる現実の
- p186b (8.29)が冗長な方程式を含まないためには
- p187t ...場合には、冗長な方程式を取り除くこともできる
- p187m エッシャー (Escher)「ものみの塔 (1958)」
- p188m グラフの同型判定問題
- p188m 3連結平面グラフ、効率のよいアルゴリズム
- p188m 多面体、効率よく
- p188m 同じか否か、図形認識、ノイズ
- p188b 平面に敷き詰める、タイル、周期的タイリングの数理的理論 53, 93)
- p189t 平面の正則分割、エッシャー
- p189t 図形境界を等間隔の点の列で近似
- p189m 新しい錯視立体を作る
- p189m 接続構造を線画から推定する方法も研究
- p189m 頂点辞書と呼ばれる立体に関する知識を利用