パラパラめくる『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

ぱらぱらめくる『グレブナー基底とその応用』

グレブナー基底とその応用 (共立叢書・現代数学の潮流)

グレブナー基底とその応用 (共立叢書・現代数学の潮流)

グレブナー基底の有用性と使い方 駆け足で読む『What is ... a Grobner Basis?』

グレブナー基底の定義と性質 駆け足で読む『What is ... a Grobner Basis?』

駆け足で読む『What is ... a Grobner Basis?』

2.グレブナーの扇 ぱらぱらめくる『Comutational Algebra and Combinatorics of Toric Ideals』

  • 多項式環イデアルのグレブナーの扇って何?、というのをわかるのがこの章の目的
  • グレブナー基底についての付言
    • グレブナー基底は項の順序ルールで変わることからもわかるように、色々にとれる
    • 色々な取り方は、重みづけベクトルに対応付けることができる
    • 色々な取り方に対応する重みづけベクトルはたくさんあるけれど、それが決めるのは項の順序だけで、順序の種類数は重みづけベクトルの数に比べて圧倒的に少ない
    • それはBuchberger's algorithmが順序ルールが産む違いをぱっぱと捨ててしまえるような、そんな背景があるかららしい
    • これは、ひとまず置いて置いて
  • ポリトープについて
    • 凸多面体
    • Polyhedral cone(錐)というものがある
    • Polyhedral fan(扇)はPolyhedral conesの集まりであって、cone同士が面を共有するように接しているようなもの
  • グレブナーの扇
    • イデアルの構成要素に順序があって、最初に来るのが、グレブナーの扇の最初のつかまえ方(最高次元)を決める
    • 多項式」の多項表現には複数の表記ができる
    • それは「構成の素」とする多項式を変えれば、そうなるのは容易に想像できる
    • 同じ「構成も素」を使っても、それぞれにどういう割り付けをしていくかの順序が変われば出来上がった表記も変わるだろう
    • グレブナーの扇も、そういう「貼り合わせ」が「素のセット」とその「順序」に依存して決まってくるよ、という話のようだ

1.グレブナー基底 ぱらぱらめくる『Comutational Algebra and Combinatorics of Toric Ideals』