Polytope complexes are the generalisation of polygon meshes in geo-information systems (GIS) to arbitrary dimension, and a natural concept for accessing spatio-temporal information. Complexes of each dimension have a straight-forward dimension-independent database representation called "Relational Complex". Accordingly, complex overlay is the corresponding generalisation of map overlay in GIS to arbitrary dimension. Such overlay can be computed by partitioning the cells into simplices, intersecting these and finally combine their intersections into the resulting overlay complex. Simplex partitioning, however, can expensive in dimension higher than 2. In the case of polytope complex overlay signed simplicial decomposition is an alternative. This paper presents a purely combinatoric polytope complex decomposition which ignores geometry. In particular, this method is also a decomposition method for non-convex polytopes. Geometric n-D-simplex intersection is then done by a simplified active-set-method---a well-known numerical optimisation method. "Summing" up the simplex intersections then yields the desired overlay complex.
Much work has been done on polytope decomposition, volume computation, and intersection---mostly, however, on convex polytopes represented by vertices (via convex hull) or by (intersecting) half spaces. That representations do not allow non-convex polytopes and some of the above mentioned problems (even vertex enumeration) are NP-hard if no fixed dimension upper bound is given @cite_10 . By using instead, vertices, edges, faces etc. are already enumerated as a precondition and the above problems can be avoided.
@cite_10
1016068550
Every convex polytope is both the intersection of a finite set of halfspaces and the convex hull of a finite vertex set. Transforming from the halfspaces (vertices, respectively) to the vertices (halfspaces, respectively) is called vertex enumeration (facet enumeration, respectively). It is an open problem whether there is an algorithm for these two problems polynomial in the input and the output size. For each of the known methods, this thesis develops a characterization of what constitutes an easy or difficult input. Example families of polytopes are presented that show that none of the known methods will yield a polynomial algorithm. On the other hand, a family of polytopes difficult for one class of algorithms can (sometimes) be easily solvable for another class of algorithms; the characterizations given here can be used to guide a choice of algorithms. Similarly, although the general problems of vertex and facet enumeration are equivalent by the duality of convex polytopes, for fixed polytope family and algorithm, one of these directions can be much easier than the other. This thesis presents a new class of algorithms that use the easy direction as an oracle to solve the seemingly difficult direction.