Realization Problems for Point Configurations and Polyhedral Surfaces
Dagmar Timmreck · Universitätsbibliothek der FU Berlin Hochschulschriftenstelle u. Dokumentenserver · 2015
Realization problems are a recurrent theme in Discrete Geometry. The generic realization problem can be phrased as follows: „Is there an object living in Euclidean space Rd that satisfies some given conditions?“ The most straightforward way to give a solution of such a problem is the construction of an object with the desired properties. For non-realizability the straightforward approach is complete enumeration of all possible objects and showing for each one of them that it doesn't meet the conditions given. In theory this often is possible because the discrete setting reduces to a finite number of combinatorial possibilities. However, the number of possibilities typically grows exponentially with the size of the object and thus makes this approach intractable very quickly. Therefore indirect methods and conceptual arguments are pursued. One method is to expose an „obstruction“ to realizability, i.e. a property all realizable instances have and that contradicts the given conditions. In Chapter 1 we takle a problem for point configurations in the Euclidean plane. Starting from ideas of Ungar and of Pach, Pinchasi and Sharir we present two algorithms that find in a given point configuration sets of segments which are non-parallel and primitive or non- avoiding respectively. Then we turn our attention to the Jamison-Hill catalogue of slope-critical examples which have the minimal possible number of non-parallel segments. Among these we find three examples where the two conditions listed above cannot be met simultaneously. In the other examples of the catalogue we give complete systems of non-avoiding primitive segments. In Chapter 2 we construct a family of special deformed d-cubes. To this end we streamline an approach of Ziegler and Rörig. For every dimension d >= 4 we get a cube Cd that has an increasing Hamiltonian path with respect to the last coordinate xd. At the same time Cd contains the quadrilateral surface Fd on 2d vertices constructed by McMullen, Schulz and Wills (1985) in its 2-skeleton in such a way that Fd survives the projection to the last three coordinates. The starting point for Chapter 3 is Stratified Morse Theory (SMT) as developed by Goresky and MacPherson. For polyhedral complexes in Rd and especially for polyhedral surfaces in R3 the Morse data can be obtained in a purely combinatorial way once a vertex ordering is fixed. Afterwards we go beyond pure SMT for surfaces and do a more detailed analysis of possible forms of critical points. In Chapter 4 we follow the approach of Novik that exploits the classical obstruction theory for piecewise linear embeddability to find „obstruction systems“ for geometric realizability. We associate with any simplicial complex K and any integer m a system of linear equations and inequalities. If K has a simplicial embedding in Rm then the system has an integer solution. This extends the work of Novik by using not only intersection but also linking numbers.