３次元でのドロネー三角化とボロネイ多面体化
- 平面に点を撒いて、そこに三角形埋め尽くしを作る方法にドロネー三角化があり、その双対としてボロノイ図がある。ボロノイ図では多角形充填が得られる
- その3次元版もあって、3次元空間に点を撒いて、四面体で空間を分割する。その双対がボロノイ分割で、それは多面体充填分割になる
- ボロノイ多面体の境界は、撒いた点を結ぶ線分の垂直二等分面で構成される。１つの四面体の６つの辺の垂直二等分面は1点で交わる(四面体の外心)が、その点から、四面体４頂点までの距離は等しい。ボロノイ多面体をグラフとして描くと、隣り合うドロネー四面体の外心同士を結んだものとなる
- 四面体は必ず４つの四面体と隣り合うから、このボロノイ多面体グラフは４正則グラフになる(周囲を除く)
京大学部入試数学をＲでお絵描き・ごり押しする
- 2月25日は学部入試前期日程初日。例年通り、京大でも数学の試験がありました。
- 問題と解答は予備校のサイトを参照(こちら)するとして、Ｒを使って描いたりして、どういう問題なのかを表現してみることにします
- 問１は3次関数の複素数解の話。実部も虚部もゼロになる点が解であることを図で示してみました
- 問２は、ごり押しだと計算が発散するタイプの問題。要求式を収束する形に変形することに気づけば、計算機でも収束の様子を視覚化できます。整数べき乗なら実数値になるが非整数べき乗だと複素数になる複素関数の収束として視覚化してみました
- 問３は、3次元の単位ベクトルの内積の話。条件からどういう１パラメタ設定に落とせば、図示も楽
- 問４は計算機が最も得意とする、大した個数ではない悉皆探索問題として解けます
- 問５は順列・組み合わせ問題。4ｘ4行列の場合列挙だったので、少し時間がかかりますが、計算機でしらみつぶしに計算できます
- 問６は3次元のイメージがわけば、方針が立ちやすいでしょう。Ｒで図にして、必要な関数式を導けばよいようです
- Ｒのコード
パラパラめくる『Polyhedral and Algebraic Methods in Computational Geometry』
![Polyhedral and Algebraic Methods in Computational Geometry【電子書籍】[ Michael Joswig ]](https://thumbnail.image.rakuten.co.jp/@0_mall/rakutenkobo-ebooks/cabinet/8829/2000000808829.jpg?_ex=128x128 "Polyhedral and Algebraic Methods in Computational Geometry【電子書籍】[ Michael Joswig ]")
- 目次
- １ イントロと概観
- 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:
に「ある」とみなせる
- 直線・平面・超平面は線形等式、向きを考えると線形不等式、内部・外部の区別も不等式
- 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
ペアに分ける
- 偶数個2kの互いに区別できるアイテムを2個ずつのペアに分けたい
- その場合の数は二重階乗
として計算できるが
- RのZseqパッケージのFactorial.Double()関数を使っても計算できる
library(Zseq) Factorial.Double(6)
> Factorial.Double(6) Big Integer ('bigz') object of length 6: [1] 1 1 3 15 105 945
k <- 3 2 * k -1 factorial(2*k-1)/(2^(k-1)*factorial(k-1))
行列の番地の扱い～R
- Rで行列に関して、ある条件を付けて、その２次元番地を取り出したいとする
- 逆にその２次元番地を使って、Rの要素に付値したいとする
置換行列、サイクル～R
- 置換行列ができたら、そこからサイクルを取り出したい
覚えていられない、いつも使うパッケージ～R
- PCを変えたら、Rのバージョンが遅れていてパッケージインストールがエラーになった
- 少し前までは、Rをアップデートして、インストールしておくべきパッケージの基本リストがすぐに思い出せたけれど、ヒトの名前もすぐには出てこないこの頃…、全然、パッケージ名を思い出せない！
- というわけでメモ
- Rをアップデートしたら、ひとまず回そう、パッケージインストール用関数
- このコマンドを入れておくと、紐づいたパッケージ等もあれやこれや入るので、それについては"library()"関数で表示させれば、確認できる。Rstudioを使えば"Packages"パネルに同様の情報が見られる
- コマンドはgistにファイルで上げておこう(忘れるから…)
library()
- 結果
abind Combine Multidimensional Arrays askpass Safe Password Entry for R, Git, and SSH assertthat Easy Pre and Post Assertions backports Reimplementations of Functions Introduced Since R-3.0.0 base64enc Tools for base64 encoding BH Boost C++ Header Files brew Templating Framework for Report Generation callr Call R from R car Companion to Applied Regression carData Companion to Applied Regression Data Sets cellranger Translate Spreadsheet Cell Ranges to Rows and Columns cli Helpers for Developing Command Line Interfaces clipr Read and Write from the System Clipboard clisymbols Unicode Symbols at the R Prompt coda Output Analysis and Diagnostics for MCMC colorspace A Toolbox for Manipulating and Assessing Colors and Palettes commonmark High Performance CommonMark and Github Markdown Rendering in R covr Test Coverage for Packages crayon Colored Terminal Output crosstalk Inter-Widget Interactivity for HTML Widgets curl A Modern and Flexible Web Client for R data.table Extension of `data.frame` desc Manipulate DESCRIPTION Files devtools Tools to Make Developing R Packages Easier digest Create Compact Hash Digests of R Objects DT A Wrapper of the JavaScript Library 'DataTables' e1071 Misc Functions of the Department of Statistics, Probability Theory Group (Formerly: E1071), TU Wien ellipsis Tools for Working with ... evaluate Parsing and Evaluation Tools that Provide More Details than the Default fansi ANSI Control Sequence Aware String Functions farver High Performance Colour Space Manipulation fastmap Fast Implementation of a Key-Value Store forcats Tools for Working with Categorical Variables (Factors) fs Cross-Platform File System Operations Based on 'libuv' geometry Mesh Generation and Surface Tessellation ggplot2 Create Elegant Data Visualisations Using the Grammar of Graphics gh 'GitHub' 'API' git2r Provides Access to Git Repositories glue Interpreted String Literals gmp Multiple Precision Arithmetic gtable Arrange 'Grobs' in Tables haven Import and Export 'SPSS', 'Stata' and 'SAS' Files highr Syntax Highlighting for R Source Code hms Pretty Time of Day htmltools Tools for HTML htmlwidgets HTML Widgets for R httpuv HTTP and WebSocket Server Library httr Tools for Working with URLs and HTTP igraph Network Analysis and Visualization ini Read and Write '.ini' Files jsonlite A Robust, High Performance JSON Parser and Generator for R knitr A General-Purpose Package for Dynamic Report Generation in R labeling Axis Labeling later Utilities for Scheduling Functions to Execute Later with Event Loops lazyeval Lazy (Non-Standard) Evaluation lifecycle Manage the Life Cycle of your Package Functions linprog Linear Programming / Optimization lme4 Linear Mixed-Effects Models using 'Eigen' and S4 lpSolve Interface to 'Lp_solve' v. 5.5 to Solve Linear/Integer Programs magic Create and Investigate Magic Squares magrittr A Forward-Pipe Operator for R manipulateWidget Add Even More Interactivity to Interactive Charts maptools Tools for Handling Spatial Objects markdown Render Markdown with the C Library 'Sundown' matlib Matrix Functions for Teaching and Learning Linear Algebra and Multivariate Statistics Matrix Sparse and Dense Matrix Classes and Methods MatrixModels Modelling with Sparse And Dense Matrices mcmc Markov Chain Monte Carlo MCMCpack Markov Chain Monte Carlo (MCMC) Package memoise Memoisation of Functions mime Map Filenames to MIME Types miniUI Shiny UI Widgets for Small Screens minqa Derivative-free optimization algorithms by quadratic approximation munsell Utilities for Using Munsell Colours nloptr R Interface to NLopt numbers Number-Theoretic Functions onion Octonions and Quaternions openssl Toolkit for Encryption, Signatures and Certificates Based on OpenSSL openxlsx Read, Write and Edit xlsx Files partitions Additive Partitions of Integers pbkrtest Parametric Bootstrap and Kenward Roger Based Methods for Mixed Model Comparison permutations The Symmetric Group: Permutations of a Finite Set pillar Coloured Formatting for Columns pkgbuild Find Tools Needed to Build R Packages pkgconfig Private Configuration for 'R' Packages pkgload Simulate Package Installation and Attach plyr Tools for Splitting, Applying and Combining Data polynom A Collection of Functions to Implement a Class for Univariate Polynomial Manipulations pracma Practical Numerical Math Functions praise Praise Users prettyunits Pretty, Human Readable Formatting of Quantities processx Execute and Control System Processes progress Terminal Progress Bars promises Abstractions for Promise-Based Asynchronous Programming ps List, Query, Manipulate System Processes purrr Functional Programming Tools quantreg Quantile Regression R6 Encapsulated Classes with Reference Semantics rcmdcheck Run 'R CMD check' from 'R' and Capture Results RColorBrewer ColorBrewer Palettes Rcpp Seamless R and C++ Integration RcppEigen 'Rcpp' Integration for the 'Eigen' Templated Linear Algebra Library RcppProgress An Interruptible Progress Bar with OpenMP Support for C++ in R Packages readr Read Rectangular Text Data readxl Read Excel Files rematch Match Regular Expressions with a Nicer 'API' remotes R Package Installation from Remote Repositories, Including 'GitHub' reshape2 Flexibly Reshape Data: A Reboot of the Reshape Package rex Friendly Regular Expressions rgl 3D Visualization Using OpenGL rio A Swiss-Army Knife for Data I/O rlang Functions for Base Types and Core R and 'Tidyverse' Features Ronlyryamada What the Package Does (one line, title case) roxygen2 In-Line Documentation for R rprojroot Finding Files in Project Subdirectories rstudioapi Safely Access the RStudio API rsvd Randomized Singular Value Decomposition rversions Query 'R' Versions, Including 'r-release' and 'r-oldrel' scales Scale Functions for Visualization sessioninfo R Session Information sets Sets, Generalized Sets, Customizable Sets and Intervals shiny Web Application Framework for R sourcetools Tools for Reading, Tokenizing and Parsing R Code sp Classes and Methods for Spatial Data SparseM Sparse Linear Algebra stringi Character String Processing Facilities stringr Simple, Consistent Wrappers for Common String Operations sys Powerful and Reliable Tools for Running System Commands in R testthat Unit Testing for R tibble Simple Data Frames tidyselect Select from a Set of Strings usethis Automate Package and Project Setup utf8 Unicode Text Processing vctrs Vector Helpers viridisLite Default Color Maps from 'matplotlib' (Lite Version) webshot Take Screenshots of Web Pages whisker {{mustache}} for R, Logicless Templating withr Run Code 'With' Temporarily Modified Global State xfun Miscellaneous Functions by 'Yihui Xie' xml2 Parse XML xopen Open System Files, 'URLs', Anything xtable Export Tables to LaTeX or HTML yaml Methods to Convert R Data to YAML and Back zeallot Multiple, Unpacking, and Destructuring Assignment zip Cross-Platform 'zip' Compression パッケージ （ライブラリ ‘C:/Program Files/R/R-3.6.2/library’ 中): base The R Base Package boot Bootstrap Functions (Originally by Angelo Canty for S) class Functions for Classification cluster "Finding Groups in Data": Cluster Analysis Extended Rousseeuw et al. codetools Code Analysis Tools for R compiler The R Compiler Package datasets The R Datasets Package foreign Read Data Stored by 'Minitab', 'S', 'SAS', 'SPSS', 'Stata', 'Systat', 'Weka', 'dBase', ... graphics The R Graphics Package grDevices The R Graphics Devices and Support for Colours and Fonts grid The Grid Graphics Package KernSmooth Functions for Kernel Smoothing Supporting Wand & Jones (1995) lattice Trellis Graphics for R MASS Support Functions and Datasets for Venables and Ripley's MASS Matrix Sparse and Dense Matrix Classes and Methods methods Formal Methods and Classes mgcv Mixed GAM Computation Vehicle with Automatic Smoothness Estimation nlme Linear and Nonlinear Mixed Effects Models nnet Feed-Forward Neural Networks and Multinomial Log-Linear Models parallel Support for Parallel computation in R rpart Recursive Partitioning and Regression Trees spatial Functions for Kriging and Point Pattern Analysis splines Regression Spline Functions and Classes stats The R Stats Package stats4 Statistical Functions using S4 Classes survival Survival Analysis tcltk Tcl/Tk Interface tools Tools for Package Development translations The R Translations Package utils The R Utils Package
