SIAGA: Polyhedral Geometry

Seven pictures from Applied Algebra and Geometry: Picture #3

The Society for Industrial and Applied Mathematics, SIAM, has recently released a journal of Applied Algebra and Geometry called SIAGA. The poster for the journal features seven pictures. In this blog post I will talk about the third picture. See here for my blog posts on pictures one and two. And see here for more information on the new journal.

In the first section of this post “The Context”, I’ll set the mathematical scene and in the second section “The Picture” I’ll talk about this particular image, representing Polyhedral Geometry.

Fig3big

The Context

A polyhedron is a combinatorial object that crops up in many places. For example, it is the shape of the feasible region for a linear optimization problem. It is a convex shape in d-dimensional space \mathbb{R}^d described by an intersection of finitely many closed half-spaces P = \{ x \in \mathbb{R}^n : Ax \leq b \}
where A is a d \times n matrix describing the angles of the half spaces, and b \in \mathbb{R}^d encodes their translational information.

A compatible collection of polyhedra is called a polyhedral complex. It is possible to associate a polyhedral complex to an algebraic variety, allowing us to use combinatorial tools to understand the variety. A typical way to do this is via the methods of toric geometry. This approach has been applied in areas such as phylogenetics, integer programming, economics, biochemical reaction networks and computer vision (from where this particular picture arose).

Tropical geometry gives one method, called tropicalization, for getting a polyhedral complex from an algebraic variety. The new object gives us useful information. For example, the dimension of the original variety equals that of the new polyhedral complex and the latter is much easier to compute.

Polyhedral geometry also arises at the interface with the life sciences. For instance, Gheorghe Craciun recently announced a proof of the Global Attractor Conjecture for toric dynamical systems. This result is important for systems biology, and polyhedral fans play a key role in the proof.

The Picture

This picture describes one example of using polyhedral tools to understand an algebraic variety, this shedding light on the application from which the variety arose.

In the field of computer vision, and in the real world, ‘taking a photo’ is a map from the three-dimensional world to a two-dimensional world. As any good photographer knows, the resulting features of the photo depends heavily on the angle and location of the camera.

We photograph three-dimensional projective space \mathbb{P}^3. Each camera, A, is a 3 \times 4 matrix which determines a map \mathbf{x} \mapsto A\mathbf{x} to two-dimensional projective space \mathbb{P}^2. This map tells us where each point of the original world ends up in the photograph.

More information can be gained by considering multiple cameras ( A_1 , A_2, A_3) at different locations. Then we have a map from the real world to three photographs:
\phi : \mathbb{P}^3 \dashrightarrow (\mathbb{P}^2)^3
\mathbf{x} \longmapsto (A_1 \mathbf{x}, A_2 \mathbf{x}, A_3 \mathbf{x} ).

The closure of the image of this map is an irreducible variety. For example, if the A_i are the coordinate projections, the variety in (\mathbb{P}^2)^3 is cut-out by the Gröbner basis
\{ z_0 y_2 - x_0 z_2 , z_1 x_2 - x_1 z_2, z_0 y_1 - y_0 z_1, x_0 y_1 x_2 - y_0 x_1 y_2 \} \text{ .}
When we take the initial monomials of these generators, their zero-set decomposes into seven pieces: one copy of \mathbb{P}^1 \times \mathbb{P}^1 \times\mathbb{P}^1, and six copies of \mathbb{P}^1 \times\mathbb{P}^2.

Our picture shows the three-dimensional shape we get from this zero-set when we identify each projective space \mathbb{P}^i with the i-simplex. For example, \mathbb{P}^2 corresponds to the two-dimensional simplex \Delta_2 – the triangle – under the map:

\mathbb{P}^2 \ni (x_0:x_1:x_2) \longleftrightarrow \frac{1}{x_0 + x_1 + x_2} (x_0 , x_1, x_2) \in \Delta_2

and we identify \mathbb{P}^1 with the one-dimensional simplex \Delta_1 – the unit-length line.

Our zero-set is represented by a collection of polytopes which are faces of (\Delta_2)^3. The \mathbb{P}^1 \times\mathbb{P}^1 \times\mathbb{P}^1 corresponds to \Delta_1 \times \Delta_1 \times \Delta_1. This is the dark blue cube. Each of the six pieces \mathbb{P}^2 \times\mathbb{P}^1 correspond to \Delta_2 \times \Delta_1. This gives the six triangular prisms in the picture.

Each piece has been separated a little to make it easier to see, and the close-by parallel faces show how the different parts meet. Meeting at a triangle \Delta_2 means the projective spaces meet at a copy of \mathbb{P}^2. If the shared facet is a square \Delta_1 \times \Delta_1, the projective spaces meet at a copy of \mathbb{P}^1 \times\mathbb{P}^1. The original picture, and other nice ones, can be found in the paper “A Hilbert Scheme in Computer Vision” by Aholt, Sturmfels and Thomas (2013). It was made using Michael Joswig’s software Polymake.

Advertisements

3 thoughts on “SIAGA: Polyhedral Geometry

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s