regularSubdivision -- Computes the regular cell decomposition

Synopsis

Usage:

L = regularSubdivision(P,w)

L = regularSubdivision(M,w)
Inputs:
- P, a convex polyhedron,
- w, a matrix, Row matrix containing the weights.
- M, a matrix, Matrix containing the points.
Outputs:
- L, a list, List of polyhedra or List of lists of indices indicated which points form a cell.

Description

This function computes the regular subdivision of P given by the weight vector w. This is computed by placing the i-th lattice point of P on height w_i in n+1 space, taking the convexHull of these with the ray (0,...,0,1), and projecting the compact faces into n space. Note that the polyhedron must be compact, i.e. a polytope and the length of the weight vector must be the number of lattice points.

This function can also be used to compute the regular subdivision given a matrix M of points and a weight vector w. The points are lifted to the weights given by the matrix w, and the lower envelope is computed.

i1 : P = crossPolytope 3

o1 = P

o1 : Polyhedron

i2 : w =  matrix {{1,2,2,2,2,2,1}}

o2 = | 1 2 2 2 2 2 1 |

              1        7
o2 : Matrix ZZ  <--- ZZ

i3 : L = regularSubdivision(P,w)

o3 = {Polyhedron{...1...}, Polyhedron{...1...}, Polyhedron{...1...},
     ------------------------------------------------------------------------
     Polyhedron{...1...}, Polyhedron{...1...}, Polyhedron{...1...},
     ------------------------------------------------------------------------
     Polyhedron{...1...}, Polyhedron{...1...}}

o3 : List

i4 : apply(L,vertices)

o4 = {| 0 1 0 0 |, | 0 1 0 0  |, | 0 1 0  0 |, | 0 1 0  0  |, | 0 -1 0 0 |, |
      | 0 0 1 0 |  | 0 0 1 0  |  | 0 0 -1 0 |  | 0 0 -1 0  |  | 0 0  1 0 |  |
      | 0 0 0 1 |  | 0 0 0 -1 |  | 0 0 0  1 |  | 0 0 0  -1 |  | 0 0  0 1 |  |
     ------------------------------------------------------------------------
     0 -1 0 0  |, | 0 -1 0  0 |, | 0 -1 0  0  |}
     0 0  1 0  |  | 0 0  -1 0 |  | 0 0  -1 0  |
     0 0  0 -1 |  | 0 0  0  1 |  | 0 0  0  -1 |

o4 : List

i5 : M = matrix {{1,0,1,0},{1,1,0,0}};

              2        4
o5 : Matrix ZZ  <--- ZZ

i6 : w = matrix {{1,0,0,1}};

              1        4
o6 : Matrix ZZ  <--- ZZ

i7 : S = regularSubdivision (M,w)

o7 = {{0, 1, 2}, {1, 2, 3}}

o7 : List

Ways to use regularSubdivision :

"regularSubdivision(Matrix,Matrix)"
"regularSubdivision(Polyhedron,Matrix)"

For the programmer

The object regularSubdivision is a method function.