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 2109556124 1981988453 2026302893
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. This thesis covers work on two topics: unfolding polyhedra into the plane and reconstructing polyhedra from partial information. For each topic, we describe previous work in the area and present an array of new research and results. Our work on unfolding is motivated by the problem of characterizing precisely when overlaps will occur when a polyhedron is cut along edges and unfolded. By contrast to previous work, we begin by classifying overlaps according to a notion of locality. This classification enables us to focus upon particular types of overlaps, and use the results to construct examples of polyhedra with interesting unfolding properties. The research on unfolding is split into convex and non-convex cases. In the non-convex case, we construct a polyhedron for which every edge unfolding has an overlap, with fewer faces than all previously known examples. We also construct a non-convex polyhedron for which every edge unfolding has a particularly trivial type of overlap. In the convex case, we construct a series of example polyhedra for which every unfolding of various types has an overlap. These examples disprove some existing conjectures regarding algorithms to unfold convex polyhedra without overlaps. The work on reconstruction is centered around analyzing the computational complexity of a number of reconstruction questions. We consider two classes of reconstruction problems. The first problem is as follows: given a collection of edges in space, determine whether they can be rearranged by translation only to form a polygon or polyhedron. We consider variants of this problem by introducing restrictions like convexity, orthogonality, and non-degeneracy. All of these problems are NP-complete, though some are proved to be only weakly NP-complete. We then consider a second, more classical problem: given a collection of edges in space, determine whether they can be rearranged by translation and or rotation to form a polygon or polyhedron. This problem is NP-complete for orthogonal polygons, but polynomial algorithms exist for nonorthogonal polygons. For polyhedra, it is shown that if degeneracies are allowed then the problem is NP-hard, but the complexity is still unknown for non-degenerate polyhedra. The inherent computational complexity of polygon decomposition problems is of theoretical interest to researchers in the field of computational geometry and of practical interest to those working in syntactic pattern recognition. Three polygon decomposition problems are shown to be NP-hard and thus unlikely to admit efficient algorithms. The problems are to find minimum decompositions of a polygonal region into (perhaps overlapping) convex, star-shaped, or spiral subsets. We permit the polygonal region to contain holes. The proofs are by transformation from Boolean three-satisfiability, a known NP-complete problem. Several open problems are discussed. The problem of finding a d -simplex of maximum volume in an arbitrary d -dimensional V -polytope, for arbitrary d , was shown by [GKL] in 1995 to be NP-hard. They conjectured that the corresponding problem for H -polytopes is also NP-hard. This paper presents a unified way of proving the NP-hardness of both these problems. The approach also yields NP-hardness proofs for the problems of finding d -simplices of minimum volume containing d -dimensional V - or H -polytopes. The polytopes that play the key role in the hardness proofs are truncations of simplices. A construction is presented which associates a truncated simplex to a given directed graph, and the hardness results follow from the hardness of detecting whether a directed graph has a partition into directed triangles.