Warning: There are no guarantees for the robustness of the GeoCalcLib! Please report any malfunction.

The permutahedron1 is given by the convex hull of all permutations of the coordinates of

\begin{equation} \begin{pmatrix} 1 \\ 2 \\ \vdots \\ d \end{pmatrix} \end{equation}

It is easy to see that all such vectors satisfy

\begin{equation} \begin{pmatrix} 1 && 1 && \cdots && 1 \end{pmatrix}x = \frac{d(d-1)}{2} \end{equation}

i.e. and therefore has a dimension of .

We use as an example. Naturally is a 3-dimensional polytope embedded in , in order to visualise it we need to project it onto . This can easily be done using a QR decomposition of . If then rotates in such a way that its first coordinate corresponds to . We can drop the first coordinate and study at the convex hull of 3-dimensional vectors.

In Matlab we can use

V = [kron((1:4)',ones(64,1)),repmat(kron((1:4)',ones(16,1)),4,1),repmat(kron((1:4)',ones(4,1)),16,1),repmat(kron(ones(4,1),(1:4)'),16,1)];

idx = false(256,1);
for i = 1:256
    if length(unique(V(i,:))) == 4
        idx(i) = true;
    end
end

V = V(idx,:);

[Q,~] = qr([1,1,1,1]');

V = V*Q;
V = V(:,2:4);

K = convhull(V);
trisurf(K,V(:,1),V(:,2),V(:,3))
Matlab Figure Converted by PLOT2SVG written by Juerg Schwizer -2 -1 0 1 2 -2 -1 0 1 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2

Assume now we want to perform a projective transformation, that is we want to intersect the homogenisation of with a hyperplane . Since is a cone in simply rotating using a QR decomposition of and discarding the first coordinates would yield .

Therefore we use a facet enumeration of to produce , with that we will enumerate the vertices of

\begin{equation} T(\Pi_3,H) = \{x\in\mathbb R^4: x\in\text{homog}(\Pi_3)\wedge x\in H\} \end{equation}

Naturally such that we can again project them by using a QR decomposition.

For the numerical example assume . We use the following Matlab code:

s.rep = 'V';
s.V = V;
[PiA,Pib] = LRS(s);

homogA = [zeros(1,3),-1;...
          PiA,-Pib];
homogb = zeros(size(homogA,1),1);

clear s

s.rep = 'H';
s.Aineq = homogA;
s.bineq = homogb;
s.Aeq = [1,2,3,15];
s.beq = 1;
[TV,t] = LRS(s);

[Q,~] = qr(s.Aeq');
TV = TV*Q;
TV = TV(:,2:4);

K = convhull(TV);
trisurf(K,TV(:,1),TV(:,2),TV(:,3))
Matlab Figure Converted by PLOT2SVG written by Juerg Schwizer -0.3 -0.2 -0.1 0 0.1 0.2 -0.3 -0.2 -0.1 0 0.1 -0.15 -0.1 -0.05 0 0.05 0.1 0.15 0.2 0.25
  1. G. M. Ziegler - Lectures on Polytopes