dc.contributor.author
Timmreck, Dagmar Ingrid
dc.date.accessioned
2018-06-07T23:16:03Z
dc.date.available
2015-05-21T10:33:49.805Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/10267
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-14465
dc.description.abstract
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.
de
dc.description.abstract
Realisierungsprobleme treten in der diskreten Geometrie an den veschiedensten
Stellen auf. Die allgemeine Fragestellung ist dabei, ob es ein Objekt im
Anschauungsraum gibt, dass vorgegebene kombinatorische Bedingungen erfüllt.
Der direkte Weg, diese Frage zu beantworten, ist, ein Objekt mit den
geforderten Eigenschaften zu konstruieren. Für Nicht-Realisierbarkeit ist der
direkte Weg eine vollständige Aufzählung aller möglichen Objekte und der
Nachweis, dass keines davon die kombinatorischen Bedingungen erfüllt.
Theoretisch ist das oft möglich, da die diskrete Fragestellung nur endlich
viele kombinatorische Möglichkeiten zulässt. In der Praxis scheitert dieser
Ansatz an der exponentiell mit der Größe des Objekts wachsenden Anzahl an
Möglichkeiten. Daher braucht man alternative Methoden, um Nicht-
Realisierbarkeit nachzuweisen. In Kapitel 1 befassen wir uns mit einer
Fragestellung über Punktkonfigurationen in der Ebene. Aus Ideen von Ungar
einerseits und Pach, Pinchasi und Sharir andererseits entwickeln wir zwei
Algorithmen, die für eine gegebene Punktkonfiguration Teilmengen der
Verbindungsstrecken finden, die nicht parallel und zusätzlich primitiv oder
nicht-vermeidend sind. Danach untersuchen wir den Katalog von Jamison und
Hill, der alle bekannten Punktkonfigurationen enthält, die die minimale Anzahl
verschiedener Steigungen definieren. Unter diesen finden wir drei Beispiele,
in denen es keine Teilmenge von Verbindungsstrecken gibt, die gleichzeitig
alle Richtungen repräsentieren, nicht-vermeidend und primitiv sind. In Kapitel
2 konstruieren wir eine Familie deformierter d-dimensionaler Würfel. Für jede
Dimension d >= 4 erhalten wir einen Würfel Cd, der einen aufsteigenden
Hamiltonpfad bezüglich der letzten Koordinate xd hat. Gleichzeitig enthält Cd
die Flächen Fd auf 2d Ecken von McMullen, Schulz und Wills im 2-Skelett
derart, dass Fd die Projektion auf die letzten drei Koordinaten übersteht.
Dazu benutzen wir Ansätze von Ziegler und Rörig. Der Ausgangspunkt für Kapitel
3 ist die von Goresky und MacPherson entwickelte Stratifizierte Morse Theorie
(SMT). Für polyedrische Komplexe in Rd zeigen wir, dass die Morsedaten nur aus
der Eckenreihenfolge und den kombinatorischen Daten gewonnen werden können.
Anschließend gehen wir für polyedrische Flächen im R3 über die reine SMT
hinaus und untersuchen genauer, wie kritische Punkte aussehen können und
welche Effekte sie haben. In Kapitel 4 folgen wir einem Ansatz von Novik, der
die klassische Hindernistheorie für stückweise lineare Einbettbarkeit nutzt,
um „Hindernissysteme'“ für geometrische Realisierbarkeit anzugeben. Wir
konstruieren zu einem gegebenen Simplizialkomplex K und ganzzahliges m ein
System linearer Gleichungen und Ungleichungen. Wenn K eine simpliziale
Einbettung in Rm hat, dann hat das System eine ganzzahlige Lösung. Die
Bedingungen bei Novik rühren von Schnittzahlen her. In dieser Arbeit
beschreiben wir, wie wir zusätzliche Bedingungen aus Verschlingungszahlen
erhalten.
de
dc.format.extent
VIII, 101 S.
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject
deformed cubes
dc.subject
polyhedral surfaces
dc.subject
obstruction theory
dc.subject.ddc
500 Naturwissenschaften und Mathematik
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik::514 Topologie
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik::516 Geometrie
dc.title
Realization Problems for Point Configurations and Polyhedral Surfaces
dc.contributor.contact
timmreck@math.fu-berlin.de
dc.contributor.firstReferee
Prof. Günter M. Ziegler
dc.contributor.furtherReferee
Prof. Ulrich Brehm
dc.date.accepted
2014-06-23
dc.identifier.urn
urn:nbn:de:kobv:188-fudissthesis000000098987-0
dc.title.translated
Realisierungsprobleme für Punktkonfigurationen und Polyedrische Flächen
de
refubium.affiliation
Mathematik und Informatik
de
refubium.mycore.fudocsId
FUDISS_thesis_000000098987
refubium.mycore.derivateId
FUDISS_derivate_000000016798
dcterms.accessRights.dnb
free
dcterms.accessRights.openaire
open access