The Geometry Junkyard

Euler's Formula, Proof 12: Shelling

Ziegler interprets a polyhedron or polytope as a complex of polyhedral faces of varying dimensions. He lets fi denote the number of faces of dimension i, so f0=V, f1=E, and f2=F, but he also adds faces of dimension d (the whole polytope) and -1 (the empty face); f-1=fd=1. Ziegler defines a shelling of a complex of polyhedral faces to be a linear ordering on the maximal-dimension faces (facets) such that, if the facets are of dimension at least one, the ordering satisfies the following properties:
  1. The boundary of the first facet F0 has a shelling.
  2. The intersection of each facet Fj (j > 0) with the union of previous facets is nonempty and forms the prefix of a shelling of Fj.
Every convex polytope has a shelling found by traveling in a straight line from some point near one face of the polyhedron, and ordering the faces by the sequence of points at which the line crosses the plane of a face and the face becomes visible. (The line must be imagined to pass "to infinity and beyond" through to the other side of the polyhedron.) The intersection of a facet Fj with previous facets can be found geometrically as the portion of the boundary of the facet visible from the intersection point of the viewing line with the plane of the facet; this shows that the lower-dimensional shelling required by property 2 is of the same geometric type. Ziegler then proves that any polytope has Euler characteristic X(P)=Sum(-1i fi)=0, by an induction on dimension and shelling length:
The base case, in which f-1=f0=1, is clear. Now if P is a d-polytope with shelling order F1,F2,... then we have more precisely that X(F1 u F2 u ... u Fj) is 0 for j < fd-1 and 1 for j = fd-1 which follows by induction on j, since the facets we add in are (d-1)-polytopes, the Euler characteristic is additive, and the intersection of Fj with previous facets is a shellable part of, but (for j < fd-1) not the whole boundary of Fj (Ziegler shows that this last observation is true in general, but it is evident geometrically for the shelling defined above).
Removing the two "extra" faces f-1 and f3 from this sum gives us the usual Euler formula.

Proofs of Euler's Formula.
From the Geometry Junkyard, computational and recreational geometry pointers.
David Eppstein, Theory Group, ICS, UC Irvine.

Semi-automatically filtered from a common source file. Last update: Sunday, 27-Jan-2013 12:07:01 PST.