General Computational Background

To ‘express’ a polytope or simplex below we imagine a computational mechanism where a vertex is designated as an integer index into some larger array of vertices. Other polytope definitions also index into this shared array of vertices. Most of the code that deals with these indices uses them merely to test for equality, or at most exploit simple ordering of integers to sort. Coordinate data for these vertices are also available by index to some software. Without access to the array of coordinates we are dealing with abstract polytopes. The boundary of a geometric figure S is written ∂S.

Slicing a Polytope

Setting: n dimensions. We have a polytope P and a half space H. The polytope is expressed by defining its boundary as a collection of (n−1)-polytopes. We want to express the boundary of P∩H likewise. Let F be the set of (n−1)-polytopes that together bound P. The problem is thus reduced expressing the intersection of a member of F with ∂H. When we express this task as a problem in the n−1 dimensional sub-space ∂H we find a recursive situation.
Imagine a recursive routine that takes as parameters, descriptions of (1) a polytope, (2) a half space and (3) a linear function on the space, which returns the integral of the function on the intersection of the half space and the polytope.
Setting: n dimensions. (new n) Given an n-simplex S and a half space H, we want to express the boundary K of S∩H as a collection of (n−1)-simplexes.
K = ∂(S∩H) = (∂S∩H) ∪ (S∩∂H).
Let j be the number of vertices of S within H and k the number not it. j+k = n+1. The convex hull I of vertices of S that are within H is a (j−1)-simplex and the hull O of those outside is a (k−1)-simplex. ∂S is composed of n (n−1)-simplexes and unless j=0 or k=0 each of these intersect ∂H.
inactive:

First we want to decompose the boundary of the half space with the simplex into (n−1)-simplexes.

There are also jk (n−2)-simplexes which bound S and intersect H. Each of these is obtained by taking the convex hull of the set of vertices of S but one from I and one from O.

There are jk edges (1-simplexes) that intersect the boundary of the half space—one for each combination of a vertex of I and vertex of O.

Setting: n dimensions. We have a polytope P and a half space H. The polytope is expressed by defining its boundary as a collection of (n−1)-simplexes. We want to express the boundary of P∩H likewise. Let F be the set of (n−1)-simplexes that together bound P. The problem is thus reduced expressing the intersection of a member of F with H.