パラパラめくる『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
    • 射影幾何を使うのは、平行線ペアにも交点を持たせる枠組みを導入し、平行かそうでないかというような例外扱いを省略できるという利点があるようだ
    • さらに、線形計算ですべて片が付くというのも魅力
    • 射影空間の「点」は原点を通る直線(x_0:x_1:...:x_n)^Tに相当するが、射影空間での超平面は、複数の係数の同次座標的表現u_0:u_1:...:u_nになるが、射影空間の「点」は、この超平面上では、[tex:=0]を満足するようなxに「ある」とみなせる
    • 直線・平面・超平面は線形等式、向きを考えると線形不等式、内部・外部の区別も不等式
  • 3 Polytopes and Polyhedra
    • 凸多面体を扱うことにするらしい
    • モーメントカーブというものが、大事な代数幾何的要素らしい
    • モーメントカーブというのは、(t,t^2,t^3,...)という点を結んでできた曲線で、この曲線上の点を頂点とする凸多面体が(必ず?)作れるという意味で、凸多面体を扱うときに出てくるらしい
    • 3次元空間にそのようなモーメントカーブを描きつつ、その曲線上にm > 3個の点を取って、凸包を作らせて図示してみよう

f:id:ryamada:20200218181838p:plain
f:id:ryamada:20200218181848p:plain

    • Polytopeを頂点集合とそれが張る凸包と見ることもできるが、(超)平面によって囲まれたものと見ることもできる(V-表現とH-表現と呼び分ける)
    • ポセット構造も持つ
    • 内部に原点を持っていると(そのような場合をpolarityありと言うそうだ)、双対が取れて、n次元面には、k-n次元面が対応するというような対応構造が取れる
    • 組み合わせ幾何的に考えていくと、オイラーの式が(-1)^kを係数として一般型として表れる
    • 球面上の乱点からランダム多面体が作れる
    • 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
    • Non-linear にする
    • 多面体を1次線形代数でやっていたのを、高次式にして、代数多様体で考えることでNon-linearにする
  • 9 Grobner Bases and Buchberger's Algorithm