凸多面体の基礎

組み合せ論的視点からの凸多面体の教科書としては, 例えば Grünbaum の [Grü03] や Ziegler の [Zie95] といった本がある。Ziegler の本は, 多面体の基礎, 特に多面体の組み合せ論を勉強するための教科書として, よく挙げられている。 Ziegler は, 他にも [Zie07] という解説を書いている。 これは最近の話題, 特に \(f\)-vector と extremal construction についての解説であるが。

その Ziegler の [Zie07] の Appendix で紹介されているものに, polymake という software がある。UNIX 系の OS でないと動かないようであるが。解説としては, [GJ] がある。他にも, SageMath でも, 多面体を扱うことができる。

多面体といって, ほとんどの人が思い浮かべるのは, 正四面体や立方体などの正多面体だと思うが, 他に実に様々な多面体がとても幅広い分野で登場する。 目にしたものを, 次にまとめた。

• 多面体の例

凸多面体は, その名前が示すように凸集合であるが, Euclide 空間の部分空間に限らない凸集合の定義として monad を用いた Fritz の [Fri] がある。

凸多面体には, 頂点の凸包として定義するものと, 超平面により切取られた有界領域として定義するものという二つの流儀がある。 Ziegler は, 前者を \(\mathcal {V}\)-polytope, 後者を \(\mathcal {H}\)-polytope と言っている。 Ziegler によると, 凸多面体の基本定理はこの二つが同値であることである。

• \(\mathcal {V}\)-polytope の定義
• \(\mathcal {H}\)-polytope の定義
• \(\mathcal {V}\)-polytope は \(\mathcal {H}\)-polytope として表わすことができ, 逆に \(\mathcal {H}\)-polytope は \(\mathcal {V}\)-polytope として表わすことができる。

ただし, この二つが同値であるとは言っても, 具体的な多面体について, その変換を行なうのは容易ではない。この変換の問題は, convex hull problem と呼ばれている。Joswig と Ziegler の [JZ04] の Introduction を読むとよい。二つが同値であることの証明自体も面倒である。Ziegler の本には詳しい証明があるし, Gallier の [Gal] にも証明がある。

\(\mathcal {H}\)-polytope の定義を見ると, 有界性は本質的ではないように思える。\(\mathcal {H}\)-polytope の定義で有界性を仮定しないものを \(\mathcal {H}\)-polyhedron と言うが, 対応する \(\mathcal {V}\)-polyhedron を定義するためには Minkowski sum という操作が必要になる。

• Minkowski sum
• \(\mathcal {V}\)-cone と \(\mathcal {H}\)-cone

凸多面体の面 (face) は, Ziegler の本のように, 超平面を用いて定義するのが普通だろう。また余次元 \(1\) の面を facet ということも多い。

• face
• supporting hyperplane
• facet

多面体の組み合せ論的構造を表わすデータとして face lattice は基本である。

• face lattice

そのため, 多面体の比較 (同一視) の方法として, face lattice の同型がよく使われる。Combinatorially isomorphic と呼ばれる。 より精密に facet が向く方向も考慮した strongly combinatorially isomorphic という基準もある。McMullen, Schneider, Shephard の [MSS74] で導入されたものである。

• 2つの多面体が combinatorially isomorphic であること
• 2つの多面体が strongly combinatorially isomorphic であること

また, 頂点, 辺, 面等の数を順に並べた \(f\)-vector も重要なデータである。

• \(f\)-vector
• \(h\)-vector

多面体の Minkowski sum を取ったときの \(f\)-vector の評価については, Fukuda と Weibel の [FW07] がある。頂点の数を決めたときに, その面数, つまり \(f\)-vector を評価するという問題もある。これについては, McMullen [McM70] と Varnette [Bar73] の結果がある。

多面体を \(\mathcal {V}\)-polytope として考えたときに, 頂点の他にできるだけ少ないデータで多面体が表わせると便利である。 最も単純なのは, どの二つの頂点が辺で結ばれているかというデータである。 これを多面体のグラフという。

• 多面体のグラフ

3次元の場合, 多面体の展開図を作るというのは, その多面体 (の境界) をそのグラフのある spanning tree で切ることである。

• 多面体の展開図 (unfolding of polytope)

Ghomi の Notices of A.M.S. の記事 [Gho18] によると, 凸多面体の展開図がいつでもあるか, というのは, Shephard [She75] により提示された問題のようである。

高次元多面体についても, 展開図の存在は考えられていて, 最近でも Devadoss と Harvey の [DH] のような研究がある。

展開図と関係が深いのは, 測地線である。展開図の上で直線を引いて, それ以上進めなくなったら, 対応する点に移動して平行な辺を引く, という操作を繰り返せば測地線が引ける。問題としては, ある点から出発した測地線が頂点を通るか, とか, 閉測地線の分類などがある。Davis らの [Dav+] の冒頭に知られている事実が書かれている。 正多面体の場合は, Davis らの他に, Fuchs [FF07; Fuc14; Fuc16] によって調べられている。

• geodesics on polytope

多角形の場合には, 内接円や外接円の存在の問題が考えられるが, それを凸多面体に一般化したのが scribability の問題である。 Chen と Padrol の [CP17] によると, 19世紀に Steiner により3次元凸多面体の外接球, 内接球の存在の問題が提案されている, らしい。 3次元の場合, 外接球は全ての2次元面に接する球面, 内接球は全ての0次元面に接する球のことなので, 一般の次元では, 全ての \(k\)次元面に接する球の存在について議論することもできる。Schulte の [Sch87] が参照されている。Chen と Padrol は \((i,j)\)-scribable polytope の概念を導入している。

• \(k\)-scribable polytope
• weakly \(k\)-scribable polytope
• \((i,j)\)-scribable polytope

具体的に多面体を構成する際には, Billera と Sturmfels [BS92; BS94] により導入された fiber polytope は有用である。その起源となった Gel\('\)fand と Kapranov と Zelevinsky の secondary polytope [GZK89; GZK90] も重要である。

• fiber polytope と関連した話題

多面体の集まりを扱う方法としては, category にすること以外に, 次のような方法がある。

• scissors congruence
• McMullen の polytope algebra [McM89]
• Cha, Friedl, Funke の Minkowski sum による Grothendieck group [CFF17]

McMullen の polytope algebra の解説としては, Castillo の survey [Cas19] や “hands on introduction” [Cas] がある。

McMullen は, polytope algebra を用いて polytope の logarithm や exponential を定義している。

• logarithm and exponential of polytope

いわゆる双対多面体は, Ziegler の本では polar と呼ばれている。 関連した構成として, Wythoff construction がある。

• convex polytope の polar
• Wythoff construction

他に凸多面体に対する操作として次のようなものがある。

• wedge construction と wedge product (Rörig とZiegler の [RZ11])

凸多面体の deformation が Castillo と Liu の [CL22] で考えられている。

References

[Bar73]

David Barnette. “A proof of the lower bound conjecture for convex polytopes”. In: Pacific J. Math. 46 (1973), pp. 349–354.

[BS92]

Louis J. Billera and Bernd Sturmfels. “Fiber polytopes”. In: Ann. of Math. (2) 135.3 (1992), pp. 527–549. url: http://dx.doi.org/10.2307/2946575.

[BS94]

Louis J. Billera and Bernd Sturmfels. “Iterated fiber polytopes”. In: Mathematika 41.2 (1994), pp. 348–363. url: http://dx.doi.org/10.1112/S0025579300007440.

[Cas]

Federico Castillo. A pithy look at the Polytope Algebra. arXiv: 2111. 02820.

[Cas19]

Federico Castillo. “A pithy look at the polytope algebra”. In: Algebraic and geometric combinatorics on lattice polytopes. World Sci. Publ., Hackensack, NJ, 2019, pp. 117–131.

[CFF17]

Jae Choon Cha, Stefan Friedl, and Florian Funke. “The Grothendieck group of polytopes and norms”. In: Münster J. Math. 10.1 (2017), pp. 75–81. arXiv: 1512 . 06699. url: https://doi.org/10.17879/33249451813.

[CL22]

Federico Castillo and Fu Liu. “Deformation cones of nested braid fans”. In: Int. Math. Res. Not. IMRN 3 (2022), pp. 1973–2026. arXiv: 1710.01899. url: https://doi.org/10.1093/imrn/rnaa090.

[CP17]

Hao Chen and Arnau Padrol. “Scribability problems for polytopes”. In: European J. Combin. 64 (2017), pp. 1–26. arXiv: 1508.03537. url: https://doi.org/10.1016/j.ejc.2017.02.006.

[Dav+]

Diana Davis, Victor Dods, Cynthia Traub, and Jed Yang. Geodesic trajectories on regular polyhedra. arXiv: 1508.03546.

[DH]

Satyan L. Devadoss and Matthew Harvey. Unfoldings and Nets of Regular Polytopes. arXiv: 2111.01359.

[FF07]

Dmitry Fuchs and Ekaterina Fuchs. “Closed geodesics on regular polyhedra”. In: Mosc. Math. J. 7.2 (2007), pp. 265–279, 350. url: https://doi.org/10.17323/1609-4514-2007-7-2-265-279.

[Fri]

Tobias Fritz. Convex Spaces I: Definition and Examples. arXiv: 0903.5522.

[Fuc14]

Dmitry Fuchs. “Periodic billiard trajectories in regular polygons and closed geodesics on regular polyhedra”. In: Geom. Dedicata 170 (2014), pp. 319–333. url: https://doi.org/10.1007/s10711-013-9883-9.

[Fuc16]

Dmitry Fuchs. “Geodesics on regular polyhedra with endpoints at the vertices”. In: Arnold Math. J. 2.2 (2016), pp. 201–211. url: https://doi.org/10.1007/s40598-016-0040-z.

[FW07]

Komei Fukuda and Christophe Weibel. “\(f\)-vectors of Minkowski additions of convex polytopes”. In: Discrete Comput. Geom. 37.4 (2007), pp. 503–516. arXiv: math/0510470. url: https://doi.org/10.1007/s00454-007-1310-2.

[Gal]

Jean Gallier. Notes on Convex Sets, Polytopes, Polyhedra, Combinatorial Topology, Voronoi Diagrams and Delaunay Triangulations. arXiv: 0805.0292.

[Gho18]

Mohammad Ghomi. “Dürer’s unfolding problem for convex polyhedra”. In: Notices Amer. Math. Soc. 65.1 (2018), pp. 25–27.

[GJ]

Ewgenij Gawrilow and Michael Joswig. Geometric Reasoning with polymake. arXiv: math/0507273.

[Grü03]

Branko Grünbaum. Convex polytopes. Second. Vol. 221. Graduate Texts in Mathematics. Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler. Springer-Verlag, New York, 2003, pp. xvi+468. isbn: 0-387-00424-6; 0-387-40409-0. url: https://doi.org/10.1007/978-1-4613-0019-9.

[GZK89]

I. M. Gel\('\)fand, A. V. Zelevinskiı̆, and M. M. Kapranov. “Newton polyhedra of principal \(A\)-determinants”. In: Dokl. Akad. Nauk SSSR 308.1 (1989), pp. 20–23.

[GZK90]

I. M. Gel\('\)fand, A. V. Zelevinskiı̆, and M. M. Kapranov. “Discriminants of polynomials in several variables and triangulations of Newton polyhedra”. In: Algebra i Analiz 2.3 (1990), pp. 1–62.

[JZ04]

Michael Joswig and Günter M. Ziegler. “Convex hulls, oracles, and homology”. In: J. Symbolic Comput. 38.4 (2004), pp. 1247–1259. arXiv: math/0301100. url: http://dx.doi.org/10.1016/j.jsc.2003.08.006.

[McM70]

P. McMullen. “The maximum numbers of faces of a convex polytope”. In: Mathematika 17 (1970), pp. 179–184. url: https://doi.org/10.1112/S0025579300002850.

[McM89]

Peter McMullen. “The polytope algebra”. In: Adv. Math. 78.1 (1989), pp. 76–130. url: https://doi.org/10.1016/0001-8708(89)90029-7.

[MSS74]

P. McMullen, R. Schneider, and G. C. Shephard. “Monotypic polytopes and their intersection properties”. In: Geometriae Dedicata 3 (1974), pp. 99–129. url: https://doi.org/10.1007/BF00181364.

[RZ11]

Thilo Rörig and Günter M. Ziegler. “Polyhedral surfaces in wedge products”. In: Geom. Dedicata 151 (2011), pp. 155–173. arXiv: 0908. 3159. url: https://doi.org/10.1007/s10711-010-9524-5.

[Sch87]

E. Schulte. “Analogues of Steinitz’s theorem about noninscribable polytopes”. In: Intuitive geometry (Siófok, 1985). Vol. 48. Colloq. Math. Soc. János Bolyai. North-Holland, Amsterdam, 1987, pp. 503–516.

[She75]

G. C. Shephard. “Convex polytopes with convex nets”. In: Math. Proc. Cambridge Philos. Soc. 78.3 (1975), pp. 389–403. url: https://doi.org/10.1017/S0305004100051860.

[Zie07]

Günter M. Ziegler. “Convex polytopes: extremal constructions and \(f\)-vector shapes”. In: Geometric combinatorics. Vol. 13. IAS/Park City Math. Ser. Providence, RI: Amer. Math. Soc., 2007, pp. 617–691. arXiv: math/0411400.

[Zie95]

Günter M. Ziegler. Lectures on polytopes. Vol. 152. Graduate Texts in Mathematics. Springer-Verlag, New York, 1995, pp. x+370. isbn: 0-387-94365-X. url: https://doi.org/10.1007/978-1-4613-8431-1.