パラパラめくる『Polyhedral and Algebraic Methods in Computational Geometry』
- 目次
- 1 イントロと概観
- Part I Linear Computational Geometry
- 2 Geometric Fundamentals; 射影空間、射影幾何
- 3 Polytopes and Polyhedra; (超)多面体
- 4 Linear Programming
- 5 Computation of Convex Hull
- 6 Voronoi Diagrams
- 7 Delone Triangulations
- Part II Non-linear Computational Geometry
- 8 Algebraic and Geometric Foundations
- 9 Grobner Bases and Buchberger's Algorithm
- 10 Solving Systems of Polynomial Equations Using Grobner Bases
- Part III Applications
- 11 Reconstruction of Curves
- 12 Plucker Coordinates and Lines in Space
- 13 Applications of Non-linear Computational Geometry
- 2 Geometric Fundamentals
- 射影幾何を使うのは、平行線ペアにも交点を持たせる枠組みを導入し、平行かそうでないかというような例外扱いを省略できるという利点があるようだ
- さらに、線形計算ですべて片が付くというのも魅力
- 射影空間の「点」は原点を通る直線に相当するが、射影空間での超平面は、複数の係数の同次座標的表現になるが、射影空間の「点」は、この超平面上では、[tex:
=0]を満足するようなに「ある」とみなせる - 直線・平面・超平面は線形等式、向きを考えると線形不等式、内部・外部の区別も不等式
- 3 Polytopes and Polyhedra
-
- Polytopeを頂点集合とそれが張る凸包と見ることもできるが、(超)平面によって囲まれたものと見ることもできる(V-表現とH-表現と呼び分ける)
- ポセット構造も持つ
- 内部に原点を持っていると(そのような場合をpolarityありと言うそうだ)、双対が取れて、n次元面には、k-n次元面が対応するというような対応構造が取れる
- 組み合わせ幾何的に考えていくと、オイラーの式がを係数として一般型として表れる
- 球面上の乱点からランダム多面体が作れる
- Minkowski sum of a polytopeと言うのがある…要、確認
- SAGEにも入れられる polynajeなるアプリを使うと、いろいろ試せるらしい(モーメントカーブ上に点を持つ、cyclic多面体を作って、その点、線分、面、…の数を出したり、超面と頂点との関係行列を出したりできる(こちら)
- 4 Linear Programming
- 連立線形不等式が多面体を定めるので、それに基づくアルゴリズムが提唱されている
- 5 Computation of Convex Hull
- 具体的なアルゴリズム
- 6 Voronoi Diagrams
- 空間に点集合があれば、空間の任意の点を、最近点にて分割することができて、それがボロノイ分割
- n+1次元空間の開放多面体を射影するとn次元空間のボロノイ分割に対応することが、多面体におけるボロノイ分割の役割らしい
- 7 Delone Triangulations
- 8 Algebraic and Geometric Foundations
- 9 Grobner Bases and Buchberger's Algorithm