Sage中多面体计算的较长介绍

本教程旨在展示Sage关于多面体几何和组合学的一些可能性。

关于这一主题的经典文献包括:

  • 凸多面体 ,布兰科·格伦鲍姆, [Gru1967]

  • 凸多面体简介 ,阿恩·布朗斯特德, [Bro1983]

  • 多面体讲座 Günter M.齐格勒, [Zie2007]

对于命名法,Sage试图遵循:

  • 离散与计算几何手册 ,第15章, [Goo2004]

本文件的编写部分得到了OpenDreamKit项目的支持,并在奥洛特(西班牙)的SageDays 84期间编写。

第0讲:基本定义和结构

真实的 (ktimes d) -矩阵 A 一个实向量 b 在里面 mathbb{{R}}^d 定义a(凸) 多面体 P 作为线性不等式组的一组解:

\[Acdot x+bgeq 0。\]

Each row of A defines a closed half-space of mathbb{R}^d. Hence a polyhedron is the intersection of finitely many closed half-spaces in mathbb{R}^d. The matrix A may contain equal rows, which may lead to a set of equalities satisfied by the polyhedron. If there are no redundant rows in the above definition, this definition is referred to as the mathbf{H} -representation of a polyhedron.

极大仿射子空间 L 包含在多面体中的是 直线性 空间 P . 固定一个点 o 线性空间的 L 充当 起源 ,一个人可以写下每一点 p 在多面体中作为一个组合

\[p=ell+sum{i=1}^{n}lambda_iv_i+sum{i=1}^{m}mu}i,\]

在哪里? ellin L (使用) o 作为起源), sum_{{i=1}}^nlambda_i=1lambda_igeq0mu_igeq0r_ineq0 为了所有 0leq ileq m 以及 r_i 的正独立性(起源不在其正范围内)。对于一个给定的点 p 使用不同的集合可能有许多等效的方法来编写上面的内容 {{v_i}}_{{i=1}}^{{n}}{{r_i}}_{{i=1}}^{{m}} . 因此,我们要求集合是包含极小集,这样我们就可以得到任何点的上述性质相等 pin P .

The vectors v_i are called the vertices of P and the vectors r_i are called the rays of P. This way to represent a polyhedron is referred to as the mathbf{V} -representation of a polyhedron. The first sum represents the convex hull of the vertices v_i 's and the second sum represents a pointed polyhedral cone generated by finitely many rays.

当线性空间和光线被缩减到一个点(即没有光线和直线)时,对象通常被称为 多面体 .

注解

在输入时,如构造函数文档中所述 Polyhedron?

You may either define it with vertex/ray/line or inequalities/equations data, but not both. Redundant data will automatically be removed (unless "minimize=False"), and the complementary representation will be computed.

以下是的构造函数函数的文档 多面体 .

V -代表

首先,让我们将多面体对象定义为一组点和一些光线的凸包。

sage: P1 = Polyhedron(vertices = [[1, 0], [0, 1]], rays = [[1, 1]])
sage: P1
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray

字符串表示法已经提供了很多信息:

  • 多面体的维数(包含它的最小仿射空间)

  • 定义它的空间的维数

  • 底座环 (mathbb{{Z}}^2 )多面体所在的位置(这指定父类,请参见 多面体亲本

  • 顶点的数量

  • 射线的数量

当然,您想知道这个对象是什么样子的:

sage: P1.plot()
Graphics object consisting of 5 graphics primitives

我们还可以添加一个线性空间。

sage: P2 = Polyhedron(vertices = [[1/2, 0, 0], [0, 1/2, 0]],
....:                 rays = [[1, 1, 0]],
....:                 lines = [[0, 0, 1]])
sage: P2
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 2 vertices, 1 ray, 1 line
sage: P2.plot()
Graphics3d Object

请注意,基环因值而改变 frac{{1}}{{2}} . 实际上,Sage找到了一个合适的环来定义对象。

sage: P1.parent()
Polyhedra in QQ^2
sage: P2.parent()
Polyhedra in QQ^3

选择的环取决于输入格式。

sage: P3 = Polyhedron(vertices = [[0.5, 0], [0, 0.5]])
sage: P3
A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices
sage: P3.parent()
Polyhedra in RDF^2

警告

底座环 RDF 应小心使用。由于它不是一个精确的环,某些计算可能会中断或无声地产生错误的结果,例如在处理非简单多面体时。

下面的示例演示了 RDF .

sage: D = polytopes.dodecahedron()
sage: D
A 3-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^3 defined as the convex hull of 20 vertices
sage: D_RDF = Polyhedron(vertices = [n(v.vector(),digits=6) for v in D.vertices()], base_ring=RDF)
Traceback (most recent call last):
...
ValueError: *Error: Numerical inconsistency is found.  Use the GMP exact arithmetic.

如果多面体的输入由python组成 float ,它自动将数据转换为 RDF

sage: Polyhedron(vertices=[[float(1.1)]])
A 0-dimensional polyhedron in RDF^1 defined as the convex hull of 1 vertex

在代数数上定义多面体也是可能的。

sage: sqrt_2 = AA(2)^(1/2)
sage: cbrt_2 = AA(2)^(1/3)
sage: timeit('Polyhedron(vertices = [[sqrt_2, 0], [0, cbrt_2]])')  # random
5 loops, best of 3: 43.2 ms per loop
sage: P4 = Polyhedron(vertices = [[sqrt_2, 0], [0, cbrt_2]]); P4
A 1-dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices

还有另一种方法可以在代数数上创建多面体:

sage: K.<a> = NumberField(x^2 - 2, embedding=AA(2)**(1/2))
sage: L.<b> = NumberField(x^3 - 2, embedding=AA(2)**(1/3))
sage: timeit('Polyhedron(vertices = [[a, 0], [0, b]])')  # random
5 loops, best of 3: 39.9 ms per loop
sage: P5 = Polyhedron(vertices = [[a, 0], [0, b]]); P5
A 1-dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices

如果基环已知,则使用适当的 sage.rings.number_field.number_field.number_field.composite_fields()

sage: J = K.composite_fields(L)[0]
sage: timeit('Polyhedron(vertices = [[J(a), 0], [0, J(b)]])')  # random
25 loops, best of 3: 9.8 ms per loop
sage: P5_comp = Polyhedron(vertices = [[J(a), 0], [0, J(b)]]); P5_comp
A 1-dimensional polyhedron in (Number Field in ab with defining polynomial x^6 - 6*x^4 - 4*x^3 + 12*x^2 - 24*x - 4 with ab = -0.1542925124782219?)^2 defined as the convex hull of 2 vertices

多面体计算 Symbolic Ring 没有实现。无法在其上定义多面体:

sage: sqrt_2s = sqrt(2)
sage: cbrt_2s = 2^(1/3)
sage: Polyhedron(vertices = [[sqrt_2s, 0], [0, cbrt_2s]])
Traceback (most recent call last):
...
ValueError: no default backend for computations with Symbolic Ring

同样,也不可能在上面创建多面体对象 RR (不管精确到多少位)。

sage: F45 = RealField(45)
sage: F100 = RealField(100)
sage: f = 1.1
sage: Polyhedron(vertices=[[F45(f)]])
Traceback (most recent call last):
...
ValueError: the only allowed inexact ring is 'RDF' with backend 'cdd'
sage: Polyhedron(vertices=[[F100(f)]])
Traceback (most recent call last):
...
ValueError: the only allowed inexact ring is 'RDF' with backend 'cdd'

有一个例外,当精度位数为53时,基环转换为 RDF

sage: F53 = RealField(53)
sage: Polyhedron(vertices=[[F53(f)]])
A 0-dimensional polyhedron in RDF^1 defined as the convex hull of 1 vertex
sage: type(Polyhedron(vertices=[[F53(f)]]))
<class 'sage.geometry.polyhedron.parent.Polyhedra_RDF_cdd_with_category.element_class'>

这种行为可能被视为错误,但它允许Sage接受以下行为:

sage: Polyhedron([(1.0, 2.3), (3.5, 2.0)])
A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices

没有指定基环 RDF 由用户决定。

H -代表

如果多面体对象是通过 V -代表,Sage可以提供 H -对象的表示。

sage: for h in P1.Hrepresentation():
....:     print(h)
An inequality (1, 1) x - 1 >= 0
An inequality (1, -1) x + 1 >= 0
An inequality (-1, 1) x + 1 >= 0

每行给出一行矩阵 A 以及向量的一个条目 b . 变量 x 是环境空间中的向量,其中 P1 已定义。这个 H -表示可以包含以下等式:

sage: P3.Hrepresentation()
(An inequality (-2.0, 0.0) x + 1.0 >= 0,
 An inequality (1.0, 0.0) x + 0.0 >= 0,
 An equation (1.0, 1.0) x - 0.5 == 0)

通过its构造多面体对象 H -表示,需要精确的格式。每个不平等 (a_{{i1}}, dots, a_{{id}})cdot x + b_i geq 0 必须写成 [b_i,a_i1, ..., a_id] .

sage: P3_H = Polyhedron(ieqs = [[1.0, -2, 0], [0, 1, 0]], eqns = [[-0.5, 1, 1]])
sage: P3 == P3_H
True
sage: P3_H.Vrepresentation()
(A vertex at (0.0, 0.5), A vertex at (0.5, 0.0))

值得使用该参数 eqns 缩短对象的结构。在下面的示例中,前四行是第二组四行的负数。

sage: H = [[0, 0, 0, 0, 0, 0, 0, 0, 1],
....:  [0, 0, 0, 0, 0, 0, 1, 0, 0],
....:  [-2, 1, 1, 1, 1, 1, 0, 0, 0],
....:  [0, 0, 0, 0, 0, 0, 0, 1, 0],
....:  [0, 0, 0, 0, 0, 0, 0, 0, -1],
....:  [0, 0, 0, 0, 0, 0, -1, 0, 0],
....:  [2, -1, -1, -1, -1, -1, 0, 0, 0],
....:  [0, 0, 0, 0, 0, 0, 0, -1, 0],
....:  [2, -1, -1, -1, -1, 0, 0, 0, 0],
....:  [0, 0, 0, 0, 1, 0, 0, 0, 0],
....:  [0, 0, 0, 1, 0, 0, 0, 0, 0],
....:  [0, 0, 1, 0, 0, 0, 0, 0, 0],
....:  [-1, 1, 1, 1, 1, 0, 0, 0, 0],
....:  [1, 0, 0, -1, 0, 0, 0, 0, 0],
....:  [0, 1, 0, 0, 0, 0, 0, 0, 0],
....:  [1, 0, 0, 0, -1, 0, 0, 0, 0],
....:  [1, 0, -1, 0, 0, 0, 0, 0, 0],
....:  [1, -1, 0, 0, 0, 0, 0, 0, 0]]
sage: timeit('Polyhedron(ieqs = H)')  # random
125 loops, best of 3: 5.99 ms per loop
sage: timeit('Polyhedron(ieqs = H[8:], eqns = H[:4])')  # random
125 loops, best of 3: 4.78 ms per loop
sage: Polyhedron(ieqs = H) == Polyhedron(ieqs = H[8:], eqns = H[:4])
True

当然,这是一个很有趣的例子,但是如果可能的话,在定义多面体之前通常需要对数据进行预处理。

第一讲:表现对象

许多对象与 H -和 V -陈述。Sage为他们实现了类。

H -代表

您可以存储 H -表示变量,并将不等式和等式用作对象。

sage: P3_QQ = Polyhedron(vertices = [[0.5, 0], [0, 0.5]], base_ring=QQ)
sage: HRep = P3_QQ.Hrepresentation()
sage: H1 = HRep[0]; H1
An equation (2, 2) x - 1 == 0
sage: H2 = HRep[1]; H2
An inequality (0, -2) x + 1 >= 0
sage: H1.<tab>   # not tested
sage: H1.A()
(2, 2)
sage: H1.b()
-1
sage: H1.is_equation()
True
sage: H1.is_inequality()
False
sage: H1.contains(vector([0,0]))
False
sage: H2.contains(vector([0,0]))
True
sage: H1.is_incident(H2)
True

可以获得 H -陈述如下。

sage: P3_QQ.equations()
(An equation (2, 2) x - 1 == 0,)
sage: P3_QQ.inequalities()
(An inequality (0, -2) x + 1 >= 0, An inequality (0, 1) x + 0 >= 0)

注解

建议使用 equationsequation_generator (对于不等式也是如此)如果你想迭代它们而不是 equations_list .

V -代表

类似地,您可以访问多面体的顶点、光线和线。

sage: VRep = P2.Vrepresentation(); VRep
(A line in the direction (0, 0, 1),
 A vertex at (0, 1/2, 0),
 A vertex at (1/2, 0, 0),
 A ray in the direction (1, 1, 0))
sage: L = VRep[0]; L
A line in the direction (0, 0, 1)
sage: V = VRep[1]; V
A vertex at (0, 1/2, 0)
sage: R = VRep[3]; R
A ray in the direction (1, 1, 0)
sage: L.is_line()
True
sage: L.is_incident(V)
True
sage: R.is_incident(L)
False
sage: L.vector()
(0, 0, 1)
sage: V.vector()
(0, 1/2, 0)

可以获得 V -陈述如下。

sage: P2.vertices()
(A vertex at (0, 1/2, 0), A vertex at (1/2, 0, 0))
sage: P2.rays()
(A ray in the direction (1, 1, 0),)
sage: P2.lines()
(A line in the direction (0, 0, 1),)

sage: P2.vertices_matrix()
[  0 1/2]
[1/2   0]
[  0   0]

注解

建议使用 verticesvertex_generator (光线和线条也是如此)如果你想迭代它们而不是 vertices_list .

第二讲:多面体计算的后端

为了处理多面体对象,Sage目前有四个后端可用。这些后端提供了各种功能,并有自己的特定优势和局限性。

默认后端是 ppl . 任何需要的时候 速度 尝试不同的后端是很好的。后端 fieldnot 专门设计用于处理极值计算,但可以在精确坐标下进行计算。

这个 cdd 后端

为了使用特定的后端,我们指定 backend 参数。

sage: P1_cdd = Polyhedron(vertices = [[1, 0], [0, 1]], rays = [[1, 1]], backend='cdd')
sage: P1_cdd
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray

一个先验,似乎没有什么改变,但是。。。

sage: P1_cdd.parent()
Polyhedra in QQ^2

多面体 P1_cdd 现在被后端视为有理多面体 cdd . 我们也可以使用 type

sage: type(P1_cdd)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_cdd_with_category.element_class'>
sage: type(P1)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_ppl_with_category.element_class'>

我们看到了

  • 使用的后端(例如: backend_cdd

  • 后面跟着一个点“.”

  • 母公司(例如: Polyhedra_QQ )接着是后端,

在本教程中,您可以放心地忽略其余部分。

这个 cdd 后端也接受 RDF

sage: P3_cdd = Polyhedron(vertices = [[0.5, 0], [0, 0.5]], backend='cdd')
sage: P3_cdd
A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices

但不是代数或符号值:

sage: P4_cdd = Polyhedron(vertices = [[sqrt_2, 0], [0, cbrt_2]], backend='cdd')
Traceback (most recent call last):
...
ValueError: No such backend (=cdd) implemented for given basering (=Algebraic Real Field).

sage: P5_cdd = Polyhedron(vertices = [[sqrt_2s, 0], [0, cbrt_2s]], backend='cdd')
Traceback (most recent call last):
...
ValueError: No such backend (=cdd) implemented for given basering (=Symbolic Ring).

有可能得到 cdd 上定义的任何多面体对象的格式 mathbb{{Z}}mathbb{{Q}}RDF

sage: print(P1.cdd_Vrepresentation())
V-representation
begin
 3 3 rational
 0 1 1
 1 0 1
 1 1 0
end
sage: print(P3.cdd_Hrepresentation())
H-representation
linearity 1 1
begin
 3 3 real
 -0.5 1.0 1.0
 1.0 -2.0 0.0
 0.0 1.0 0.0
end

也可以使用方法将这些数据写入文件 .write_cdd_Hrepresentation(filename).write_cdd_Vrepresentation(filename) 在哪里 filename 包含要写入的文件的路径的字符串。

这个 ppl 后端

多面体对象的默认后端是 ppl .

sage: type(P1)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_ppl_with_category.element_class'>
sage: type(P2)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_ppl_with_category.element_class'>
sage: type(P3)  # has entries like 0.5
<class 'sage.geometry.polyhedron.parent.Polyhedra_RDF_cdd_with_category.element_class'>

如您所见,它不接受 RDF 多面体构造器使用 cdd 后端。

这个 polymake 后端

这个 polymake 安装sage的实验包polymake时提供后端。

sage: p = Polyhedron(vertices=[(0,0),(1,0),(0,1)],             # optional - polymake
....:                rays=[(1,1)], lines=[],
....:                backend='polymake', base_ring=QQ)

二次域示例:

sage: V = polytopes.dodecahedron().vertices_list()
sage: Polyhedron(vertices=V, backend='polymake')               # optional - polymake
A 3-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5)^3 defined as the convex hull of 20 vertices

这个 field 后端

事实证明,有理数不足以表示多面体的所有组合类型。例如,Perles构造了一个 8 -三维多面体 12 没有有理坐标实现的顶点,参见 [Zie2007]. 此外,如果一个人想要一个实现具有特定的几何性质,例如对称性,有时还需要无理坐标。

后端 field 提供处理此类示例所需的工具。

sage: type(D)
<class 'sage.geometry.polyhedron.parent.Polyhedra_field_with_category.element_class'>

任何时候坐标都应该在理性的扩展中,后端 field 被称为。

sage: P4.parent()
Polyhedra in AA^2
sage: P5.parent()
Polyhedra in AA^2
sage: type(P4)
<class 'sage.geometry.polyhedron.parent.Polyhedra_field_with_category.element_class'>
sage: type(P5)
<class 'sage.geometry.polyhedron.parent.Polyhedra_field_with_category.element_class'>

这个 normaliz 后端

第四个后端是 normaliz 是一个可选的Sage包。

sage: P1_normaliz = Polyhedron(vertices = [[1, 0], [0, 1]], rays = [[1, 1]], backend='normaliz')  # optional - pynormaliz
sage: type(P1_normaliz)                                                                           # optional - pynormaliz
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_normaliz_with_category.element_class'>
sage: P2_normaliz = Polyhedron(vertices = [[1/2, 0, 0], [0, 1/2, 0]],                             # optional - pynormaliz
....:                 rays = [[1, 1, 0]],
....:                 lines = [[0, 0, 1]], backend='normaliz')
sage: type(P2_normaliz)                                                                           # optional - pynormaliz
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_normaliz_with_category.element_class'>

此后端不适用于 RDF 不准确的行为。

sage: P3_normaliz = Polyhedron(vertices = [[0.5, 0], [0, 0.5]], backend='normaliz')             # optional - pynormaliz
Traceback (most recent call last):
...
ValueError: No such backend (=normaliz) implemented for given basering (=Real Double Field).

这个 normaliz 后端提供代数数的快速计算。它们可以作为嵌入数域、代数数域甚至符号环的元素输入。在内部,使用嵌入的数字字段完成计算。

sage: P4_normaliz = Polyhedron(vertices = [[sqrt_2, 0], [0, cbrt_2]], backend='normaliz')       # optional - pynormaliz
sage: P4_normaliz                                                                               # optional - pynormaliz
A 1-dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices

sage: P5_normaliz = Polyhedron(vertices = [[sqrt_2s, 0], [0, cbrt_2s]], backend='normaliz')     # optional - pynormaliz
sage: P5_normaliz                                                                               # optional - pynormaliz
A 1-dimensional polyhedron in (Symbolic Ring)^2 defined as the convex hull of 2 vertices

后端 normaliz 提供其他方法,如 integral_hull ,也适用于无界多面体。

sage: P6 = Polyhedron(vertices = [[0, 0], [3/2, 0], [3/2, 3/2], [0, 3]], backend='normaliz')  # optional - pynormaliz
sage: IH = P6.integral_hull(); IH                                                             # optional - pynormaliz
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
sage: P6.plot(color='blue')+IH.plot(color='red')                                              # optional - pynormaliz
Graphics object consisting of 12 graphics primitives
sage: P1_normaliz.integral_hull()                                                             # optional - pynormaliz
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray

第三讲:对于每一个多面体,正确的父类

为了 知道多面体对象的所有方法 我们必须调查 base class

如果这些类看起来是空的,不要惊讶!这些类主要包含实现一些比较方法的私有方法:验证基环中数字的相等性和不相等性以及其他内部功能。

为了全面了解提供给您的方法, 多面体的基类 是你想去的第一个地方。

第四讲:多面体类库

类库里有很多多面体,你看 常用的、著名的或有趣的多面体的类库 . 看看它们,看看你的多面体是否已经定义好了!

sage: A = polytopes.buckyball(); A  # can take long
A 3-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^3 defined as the convex hull of 60 vertices
sage: B = polytopes.cross_polytope(4); B
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 8 vertices
sage: C = polytopes.cyclic_polytope(3,10); C
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 10 vertices
sage: E = polytopes.snub_cube(exact=False); E
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 24 vertices
sage: polytopes.<tab>  # not tested, to view all the possible polytopes

参考文献

Bro1983

布朗斯特德,A.,凸多面体导论,数学研究生教材第90卷。斯普林格·韦拉格,纽约,1983年。国际标准书号978-1-4612-7023-2

Goo2004

J、 E.Goodman和J.O'Rourke,编辑,CRC出版社有限责任公司,佛罗里达州博卡拉顿,2004年。ISBN 978-1584883012(65章,xvii+1539页)。

Gru1967

Günbaum,B.,凸多面体,数学研究生教材第221卷。斯普林格·韦拉格,纽约,2003年。国际标准书号978-1-4613-0019-9

Zie2007(1,2)

齐格勒,G.M.,关于多面体的讲座,数学研究生教材第152卷。斯普林格·韦拉格,纽约,2007年。国际标准书号978-0-387-94365-7