For a polyhedron @math P let @math B(P) denote the polytopal complex that is formed by all bounded faces of @math P. If @math P is the intersection of @math n halfspaces in @math RD, but the maximum dimension @math d of any face in @math B(P) is much smaller, we show that the combinatorial complexity of @math P cannot be too high; in particular, that it is independent of @math D. We show that the number of vertices of @math P is @math O(nd) and the total number of bounded faces of the polyhedron is @math O(nd2). For inputs in general position the number of bounded faces is @math O(nd). We show that for certain specific values of @math d and @math D, our bounds are tight. For any fixed @math d, we show how to compute the set of all vertices, how to determine the maximum dimension of a bounded face of the polyhedron, and how to compute the set of bounded faces in polynomial time, by solving a number of linear programs that is polynomial in @math n.
Bounded subcomplexes have also been investigated in other contexts. In tropical geometry, the defined by a set of points is also equivalent to the set of bounded faces of a polytope defined from the points @cite_8 . Develin @cite_15 studied the bounded faces of a certain polytope arising from a problem in algebra, and showed that they are all isomorphic to subpolytopes of permutohedra. Queyranne @cite_4 used polytopes to model scheduling problems; the polytope defined by Queyranne has a unique bounded facet. In connection with the tight span application, Hirai @cite_29 showed that the bounded faces of a halfspace intersection form a contractable complex. @cite_14 consider the problem of computing the bounded subcomplex of a polyhedron, but they do not bound the complexity of the complex. Their algorithms assume that the vertices and facets of the polyhedron are both already known, and are output-sensitive given this information.
@cite_14 @cite_4 @cite_8 @cite_29 @cite_15
1968602707 2109556124 2964067385 1486210143
Given a monomial k[x1,. . . ,xn]-module M in the Laurent polynomial ring k[x1±1, . . . , xn±1], the hull complex is defined to be the set of bounded faces of the convex hull of the points ta| xa ∈ M for sufficiently large t. Bayer and Sturmfels conjectured that the faces of this polyhedron are of bounded complexity in the sense that every such face is affinely isomorphic to a subpolytope of the (n – 1)-dimensional permutohedron, which in particular would imply that these faces have at most n! vertices. In this paper we prove that the latter statement is true, and give a counterexample to the stronger conjecture. 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. This paper is about the combinatorics of finite point configurations in the tropical projective space or, dually, of arrangements of finitely many tropical hyperplanes. Moreover, arrangements of finitely many tropical halfspaces can be considered via coarsenings of the resulting polyhedral decompositions of Rd. This leads to natural cell decompositions of the tropical projective space TPmind−1. Our method is to employ a known class of ordinary convex polyhedra naturally associated with weighted digraphs. This way we can relate to and use results from combinatorics and optimization. One outcome is the solution of a conjecture of Develin and Yu (2007). This paper tackles the problem of computing topological invariants of geometric objects in a robust manner, using only point cloud data sampled from the object. It is now widely recognised that this kind of topological analysis can give qualitative information about data sets which is not readily available by other means. In particular, it can be an aid to visualisation of high dimensional data. Standard simplicial complexes for approximating the topological type of the underlying space (such as Cech, Rips, or a-shape) produce simplicial complexes whose vertex set has the same size as the underlying set of point cloud data. Such constructions are sometimes still tractable, but are wasteful (of computing resources) since the homotopy types of the underlying objects are generally realisable on much smaller vertex sets. We obtain smaller complexes by choosing a set of 'landmark' points from our data set, and then constructing a "witness complex" on this set using ideas motivated by the usual Delaunay complex in Euclidean space. The key idea is that the remaining (non-landmark) data points are used as witnesses to the existence of edges or simplices spanned by combinations of landmark points. Our construction generalises the topology-preserving graphs of Martinetz and Schulten [MS94] in two directions. First, it produces a simplicial complex rather than a graph. Secondly it actually produces a nested family of simplicial complexes, which represent the data at different feature scales, suitable for calculating persistent homology [ELZ00, ZC04]. We find that in addition to the complexes being smaller, they also provide (in a precise sense) a better picture of the homology, with less noise, than the full scale constructions using all the data points. We illustrate the use of these complexes in qualitatively analyzing a data set of 3 × 3 pixel patches studied by David [LPM03].