Introducción a politopos en Sage

Este tutorial tiene como objectivo mostrar algunas de los posibles usos de Sage con politopos.

$V$-representación

Primero, vamos a definir un politopo (polihedro) como la envoltura convexa de un conjunto de vértices (y rayos).


In [12]:
P0 = Polyhedron(vertices = [[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 1]])

In [13]:
P0


Out[13]:
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices (use the .plot() method to plot)

In [1]:
P1 = Polyhedron(vertices = [[1, 0], [0, 1]], rays = [[1, 1]])

In [2]:
P1


Out[2]:

El texto que aparece al definir un politopo nos da mucha información acerca del politopo:

  • la dimensión del polyhedro (el espacio mas pequeño que lo contiene)
  • la dimensión del espacio donde esta definido
  • el anillo de base ($\mathbb{Z}^2$) sobre el cual vive el politopo
  • el número de vértices
  • el numéro de rayos

Por supuesto, deseamos ver el objecto:


In [11]:
P0.plot()


Out[11]:

In [3]:
P1.plot()


Out[3]:

Podemos ver todos los métodos disponibles escribiendo P1. + tecla tab.


In [4]:
P1. # ponga el cursor despues del punto y presione la tecla Tab


  File "<ipython-input-4-e38a54d2cd64>", line 1
    P1.
       ^
SyntaxError: invalid syntax

In [5]:
P2 = Polyhedron(vertices = [[1/2, 0, 0], [0, 1/2, 0]],rays = [[1, 1, 0]],lines = [[0, 0, 1]])

In [6]:
P2


Out[6]:
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 2 vertices, 1 ray, 1 line (use the .plot() method to plot)

In [7]:
P1.parent()


Out[7]:
Polyhedra in ZZ^2

In [8]:
P2.parent()


Out[8]:
Polyhedra in QQ^3

$H$-representación

Si un polihedro fue construido via una $V$-representación, Sage puede propocionarle la $H$-representación del objeto.


In [14]:
for h in P1.Hrepresentation():
    print(h)


An inequality (1, 1) x - 1 >= 0
An inequality (0, -1) x + 1 >= 0
An inequality (-1, 0) x + 1 >= 0

Cada línea da una fila de la matriz $A$ y una entrada del vector $b$. La variable $x$ es el vector en el espacio donde $P1$ está definido. La $H$-representación puede contener ecuaciones:

La construcción de un politopo a traves de su $H$-representación, requiere un formato preciso. Cada desigualdad $(a_{i1},\ldots,a_{id})⋅x+bi\geq 0$ debe ser escrita como $[b_i,a_{i1}, \ldots, a_{id}]$.

Vale la pena utilizar el parametro egns para reducir la construcción del objeto. En el siguiente ejemplo, las primeras cuatro filas son el negativo del segundo grupo de cuatro filas.

Como aprendimos de la clase, los ejemplos son muy importantes. Sage ha implementado varios ejemplos: http://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/polyhedron/library.html"

Representación de objetos

Varios objetos están relacionados a la $H$- y $V$-representación. Sage tiene clases implementadas para esto.

$H$-representación

Puede almacenar la $H$-representación en una variable y utilizar las desigualdades como objetos.


In [15]:
P3_QQ = Polyhedron(vertices = [[0.5, 0], [0, 0.5]], base_ring=QQ)

In [16]:
HRep = P3_QQ.Hrepresentation()

In [17]:
H1 = HRep[0]; H1


Out[17]:
An equation (2, 2) x - 1 == 0

In [18]:
H2 = HRep[1]; H2


Out[18]:
An inequality (0, -2) x + 1 >= 0

In [19]:
H1.A()


Out[19]:
(2, 2)

In [20]:
H1.b()


Out[20]:
-1

In [21]:
H1.is_equation()


Out[21]:
True

In [22]:
H1.is_inequality()


Out[22]:
False

In [23]:
H1.contains(vector([0,0]))


Out[23]:
False

In [24]:
H2.contains(vector([0,0]))


Out[24]:
True

In [25]:
H1.is_incident(H2)


Out[25]:
True

Es posible obtener los diferentes objetos de la H-representación de la siguiente manera.


In [26]:
P3_QQ.equations()


Out[26]:
(An equation (2, 2) x - 1 == 0,)

In [27]:
P3_QQ.inequalities()


Out[27]:
(An inequality (0, -2) x + 1 >= 0, An inequality (0, 1) x + 0 >= 0)

$V$-representación

De forma similar, uno puede acceder a los vértices, rayos y líneas del polihedro.


In [28]:
VRep = P2.Vrepresentation(); VRep


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-28-f497fef62269> in <module>()
----> 1 VRep = P2.Vrepresentation(); VRep

NameError: name 'P2' is not defined

In [ ]:
L = VRep[0]; L

In [ ]:
V = VRep[1]; V

In [29]:
R = VRep[3]; R


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-29-bb9e9a09964a> in <module>()
----> 1 R = VRep[Integer(3)]; R

NameError: name 'VRep' is not defined

In [30]:
L.is_line()


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-30-ad2b867ba227> in <module>()
----> 1 L.is_line()

NameError: name 'L' is not defined

In [31]:
L.is_incident(V)


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-31-d6fdd08f3f9d> in <module>()
----> 1 L.is_incident(V)

NameError: name 'L' is not defined

In [32]:
R.is_incident(L)


---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-32-ffc91612287c> in <module>()
----> 1 R.is_incident(L)

AttributeError: type object 'R' has no attribute 'is_incident'

In [33]:
L.vector()


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-33-7225a008dcee> in <module>()
----> 1 L.vector()

NameError: name 'L' is not defined

In [34]:
V.vector()


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-34-de748320ff60> in <module>()
----> 1 V.vector()

NameError: name 'V' is not defined

Es posible obtener las diferentes objetos de la $V$-representación de la siguiente manera.


In [35]:
P2.vertices()


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-35-b50dbc554973> in <module>()
----> 1 P2.vertices()

NameError: name 'P2' is not defined

In [36]:
P2.rays()


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-36-36595d13e194> in <module>()
----> 1 P2.rays()

NameError: name 'P2' is not defined

In [37]:
P2.lines()


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-37-bb07c037937b> in <module>()
----> 1 P2.lines()

NameError: name 'P2' is not defined

In [38]:
P2.vertices_matrix()


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-38-cdd9d0414322> in <module>()
----> 1 P2.vertices_matrix()

NameError: name 'P2' is not defined

In [ ]:


In [ ]:

Ejercicio A

En este ejercicio, usted construirá el cuboctahedro de varias maneras y verificará que tienen el mismo tipo combinatorio.

1) La primera opción es verificar si están en la librería: http://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/polyhedron/library.html. ¡Si está! Entonces podemos utilizar la construcción dada.


In [39]:
CO = polytopes.cuboctahedron()

Veamos si en verdad se parece a lo que esperamos:


In [40]:
CO.plot()


Out[40]:

Podemos pedir el $f$-vector del cuboctahedro:


In [41]:
CO.f_vector()


Out[41]:
(1, 12, 24, 14, 1)

2) La segunda construcción utiliza el hecho de que podemos cortar los vértices por un nuevo hiperplano que atraviese las aristas exactamente en el punto medio.


In [42]:
Cube = polytopes.cube()

In [43]:
EC = Cube.edge_truncation(1/2)


/Applications/SageMath/local/lib/python2.7/site-packages/sage/repl/ipython_kernel/__main__.py:1: DeprecationWarning: edge_truncation is deprecated. Please use truncation instead.
See http://trac.sagemath.org/18128 for details.
  from ipykernel.kernelapp import IPKernelApp

Solo para verificar, calculemos el $f$-vector:


In [44]:
EC.f_vector()


Out[44]:
(1, 12, 24, 14, 1)

Pero como sabemos, dos politopos diferentes pueden tener el mismo f-vector, asi que debemos verificar si son isomorfos combinatoriamente:


In [45]:
EC.is_combinatorially_isomorphic(CO)


Out[45]:
True

!Genial!

Ahora solo para entender la construcción de una mejor manera, visualicemos el corte usual:


In [46]:
TC = Cube.truncation()

In [47]:
TC.show()


3) La tercera construcción utiliza unos trucos bonitos que podemos hacer en Sage.

Podemos tomar el polar dual del cubo, que nos da el octahedro, y ampliarlo por un factor de 2:


In [48]:
OC = 2*Cube.polar()

Luego, podemos tomar otra vez la intersección con el cubo :


In [49]:
ECCO = Cube & OC

Que politopo es ECCO?


In [50]:
ECCO.is_combinatorially_isomorphic(EC)


Out[50]:
True

!Eso es todo! Encontramos tres maneras de construir el cuboctahedro.

  • Pregunta: ¿Tienen todos el mismo número de vértices?
  • Pregunta: ¿Qué politopos obtenemos si dilatamos el octahedro por solo un factor de 3/2 en vez de 2?
  • ¿Puede identificar el politopo de la anterior parte en libreria de politopos. Verifique si con isomórficos.

Ejercisio B

Escoja cinco ejemplos discutidos en la clase que esten en la lista: http://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/polyhedron/library.html" y visualicelos, encuentre la $V$-representación, la $H$-representación, y el $f$-vector


In [ ]:


In [ ]:


In [ ]:


In [ ]: