Search

We discuss a PL analogue of Morse theory for PL manifolds. There are several notions of regular and critical points. A point is homologically regular if the homology does not change when passing through its level, it is strongly regular if the function can serve as one coordinate in a chart. Several criteria for strong regularity are presented. In particular we show that in low dimensions $d \leq 4$ a homologically regular point on a PL $d$-manifold is always strongly regular. Examples show that this fails to hold in higher dimensions $d \geq 5$. One of our constructions involves an 8-vertex embedding of the dunce hat into a polytopal 4-sphere with 8 vertices such that a regular neighborhood is Mazur's contractible 4-manifold., 24 pages, 3 figures

We survey a few strengthenings and generalizations of the Combinatorial Nullstellensatz of Alon and the Schwartz-Zippel Lemma. These lemmas guarantee the existence of (a certain number of) nonzeros of a multivariate polynomial when the variables run independently through sufficiently large ranges., Comment: 19 pages, 3 figures

We classify the finite groups of orthogonal transformations in 4-space, and we study these groups from the viewpoint of their geometric action, using polar orbit polytopes. For one type of groups (the toroidal groups), we develop a new classification based on their action on an invariant torus, while we rely on classic results for the remaining groups. As a tool, we develop a convenient parameterization of the oriented great circles on the 3-sphere, which leads to (oriented) Hopf fibrations in a natural way., Comment: 109 pages, 56 figures, 18 tables

A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate popular faces in an arrangement by inserting a single additional curve. This turns out to be already NP-hard; however, we present a probabilistic FPT-approach in the number of such faces., Comment: 23 Pages, 16 Figures, contains appendix

Given three points in the plane, we construct the plane geometric network of smallest geometric dilation that connects them. The geometric dilation of a plane network is defined as the maximum dilation (distance along the network divided by Euclidean distance) between any two points on its edges. We show that the optimum network is either a line segment, a Steiner tree, or a curve consisting of two straight edges and a segment of a logarithmic spiral., Journal of Computational Geometry, Vol. 10 No. 1 (2019)

A tree with $n$ vertices has at most $95^{n/13}$ minimal dominating sets. The growth constant $\lambda = \sqrt[13]{95} \approx 1.4194908$ is best possible. It is obtained in a semi-automatic way as a kind of "dominant eigenvalue" of a bilinear operation on sixtuples that is derived from the dynamic-programming recursion for computing the number of minimal dominating sets of a tree. We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between successive solutions., Comment: 41 pages, 21 figures, 4 tables; Python programs for certifying the upper-bound proof of Theorem 1.1 are included in the source bundle

Our goal is to compare two planar point sets by finding subsets of a given size such that a minimum-weight matching between them has the smallest weight. This can be done by a translation of one set that minimizes the weight of the matching. We give efficient algorithms (a) for finding approximately optimal matchings, when the cost of a matching is the $L_p$-norm of the tuple of the Euclidean distances between the pairs of matched points, for any $p\in [1,\infty]$, and (b)~for constructing small-size approximate minimization (or matching) diagrams: partitions of the translation space into regions, together with an approximate optimal matching for each region., 13 pages, 2 figures

For a given sequence of numbers, we want to find a monotonically increasing sequence of the same length that best approximates it in the sense of minimizing the weighted sum of absolute values of the differences. A conceptually easy dynamic programming approach leads to an algorithm with running time O(n log n). While other algorithms with the same running time are known, our algorithm is very simple. The only auxiliary data structure that it requires is a priority queue. The approach extends to other error measures.

The Koebe-Andreev-Thurston Circle Packing Theorem states that every triangulated planar graph has a contact representation by circles. The theorem has been generalized in various ways. The most prominent generalization assures the existence of a primal-dual circle representation for every 3-connected planar graph. We present a simple and elegant elementary proof of this result.

Given a set of points in the plane, we want to establish a connection network between these points that consists of several disjoint layers. Motivated by sensor networks, we want that each layer is spanning and plane, and that no edge is very long (when compared to the minimum length needed to obtain a spanning graph). We consider two different approaches: first we show an almost optimal centralized approach to extract two graphs. Then we show a constant factor approximation for a distributed model in which each point can compute its adjacencies using only local information. In both cases the obtained layers are plane, Comment: Preliminary version appeared in the proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 64, pp. 9:1-9:12

We generalize regular subdivisions (polyhedral complexes resulting from the projection of the lower faces of a polyhedron) introducing the class of recursively-regular subdivisions. Informally speaking, a recursively-regular subdivision is a subdivision that can be obtained by splitting some faces of a regular subdivision by other regular subdivisions (and continue recursively). We also define the \emph{finest regular coarsening} and the \emph{regularity tree} of a polyhedral complex. We prove that recursively-regular subdivisions are not necessarily connected by flips and that they are acyclic with respect to the in-front relation. We show that the finest regular coarsening of a subdivision can be efficiently computed, and that whether a subdivision is recursively regular can be efficiently decided. As an application, we also extend a theorem known since 1981 on illuminating space by cones and present connections of recursive regularity to tensegrity theory and graph-embedding problems., Comment: 39 pages, 14 figures

Congruence between two n-point sets in 4 dimension can be checked in O(n log n) time. On the way to establishing this result, we revisit several parts of 4-dimensional geometry, such as angles and distances between planes, Hopf fibrations, and Coxeter groups., Comment: 41 pages, 6 figures. This is the full version accompanying our paper "Congruence testing of point sets in 4-space" that is to apper at the 32st International Symposium on Computational Geometry (SoCG 2016), (LIPIcs proceedings series)

Given a graph $G=(V,E)$ with $V=\{1,\ldots,n\}$, we place on every vertex a token $T_1,\ldots,T_n$. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that token $T_i$ is on vertex $i$. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out any $2^{o(n)}$ algorithm under the ETH. This is matched with a simple $2^{O(n\log n)}$ algorithm based on a breadth-first search in an auxiliary graph. We show one general $4$-approximation and show APX-hardness. Thus, there is a small constant $\delta>1$ such that every polynomial time approximation algorithm has approximation factor at least $\delta$. Our results also hold for a generalized version, where tokens and vertices are colored. In this generalized version each token must go to a vertex with the same color., Comment: 19 pages, 10 figures

Given a graph G=(V,E) with V={1,...,n}, we place on every vertex a token T_1,...,T_n. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that token T_i is on vertex i. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out any 2^{o(n)} algorithm under the ETH. This is matched with a simple 2^{O(n*log(n))} algorithm based on a breadth-first search in an auxiliary graph. We show one general 4-approximation and show APX-hardness. Thus, there is a small constant delta > 1 such that every polynomial time approximation algorithm has approximation factor at least delta. Our results also hold for a generalized version, where tokens and vertices are colored. In this generalized version each token must go to a vertex with the same color., Leibniz International Proceedings in Informatics (LIPIcs), 57, ISSN:1868-8969, 24th Annual European Symposium on Algorithms (ESA 2016), ISBN:978-3-95977-015-6

Given a set of points in the plane, we want to establish a connection network between these points that consists of several disjoint layers. Motivated by sensor networks, we want that each layer is spanning and plane, and that no edge is very long (when compared to the minimum length needed to obtain a spanning graph). We consider two different approaches: first we show an almost optimal centralized approach to extract two trees. Then we show a constant factor approximation for a distributed model in which each point can compute its adjacencies using only local information. This second approach may create cycles, but maintains planarity., Leibniz International Proceedings in Informatics (LIPIcs), 64, ISSN:1868-8969, 27th International Symposium on Algorithms and Computation (ISAAC 2016), ISBN:978-3-95977-026-2

We give a deterministic O(n log n)-time algorithm to decide if two n-point sets in 4-dimensional Euclidean space are the same up to rotations and translations. It has been conjectured that O(n log n) algorithms should exist for any fixed dimension. The best algorithms in d-space so far are a deterministic algorithm by Brass and Knauer [Int. J. Comput. Geom. Appl., 2000] and a randomized Monte Carlo algorithm by Akutsu [Comp. Geom., 1998]. They take time O(n^2 log n) and O(n^(3/2) log n) respectively in 4-space. Our algorithm exploits many geometric structures and properties of 4-dimensional space.

We study the problem how to draw a planar graph crossing-free such that every vertex is incident to an angle greater than π. In general a plane straight-line drawing cannot guarantee this property. We present algorithms which construct such drawings with either tangent-continuous biarcs or quadratic Bézier curves (parabolic arcs), even if the positions of the vertices are predefined by a given plane straight-line drawing of the graph. Moreover, the graph can be drawn with circular arcs if the vertices can be placed arbitrarily. The topic is related to non-crossing drawings of multigraphs and vertex labeling.

The Fréchet distance between two curves is the maximum distance in a simultaneous traversal of the two curves. We refine this notion by not only looking at the maximum distance but at all other distances. Roughly speaking, we want to minimize the time T(s) during which the distance exceeds a threshold s, subject to upper speed constraints. We optimize these times lexicographically, giving more weight to larger distances s. For polygonal curves in general position, this criterion produces a unique monotone matching between the points on the two curves, which is important for applications like morphing, and we can compute this matching in polynomial time.

A polyomino (or animal) is an edge-connected set of squares on the regular square lattice. Enumeration of polyominoes is an extremely hard problem in enumerative combinatorics, with important applications in statistical physics. We investigate one of the fundamental problems related to polyominoes, namely, computing their asymptotic growth rate λ=lim A(n+1)/A(n) , where A(n) is the number of polyominoes of size n. λ is also known as Klarner's constant. The best lower and upper bounds on so far were roughly 3.98 and 4.65, respectively, meaning that not even a single decimal digit of was known. Our goal was to settle a long-standing problem: proving that λ>4. To this aim, we developed a computer program which required extremely high computing resources in terms of both running time and main memory. Our program showed rigorously that λ>4.00253.

Translating and rotating planar polygonal robots are studied in the literature for decades. An integral part of this study is the configuration space which corresponds to the work space. In the context of motion planning problems, the boundary between the free and forbidden parts of the configuration space plays a major role. In this paper we find an explicit parameterization of the boundary of the forbidden space. Using this parameterization we detail several geometrical properties of the various elements which constitute this boundary. In addition, this parameterization enables us to visualize these elements.

Constant-work-space algorithms may use only constantly many cells of storage in addition to their input, which is provided as a read-only array. We show how to construct several geometric structures efficiently in the constant-work-space model. Traditional algorithms process the input into a suitable data structure (like a doubly-connected edge list) that allows efficient traversal of the structure at hand. In the constant-work-space setting, however, we cannot afford to do this. Instead, we provide operations that compute the desired features on the fly by accessing the input with no extra space. The whole geometric structure can be obtained by using these operations to enumerate all the features. Of course, we must pay for the space savings by slower running times. While the standard data structure allows us to implement traversal operations in constant time, our schemes typically take linear time to read the input data in each step. We begin with two simple problems: triangulating a planar point set and finding the trapezoidal decomposition of a simple polygon. In both cases adjacent features can be enumerated in linear time per step, resulting in total quadratic running time to output the whole structure. Actually, we show that the former result carries over to the Delaunay triangulation, and hence the Voronoi diagram. This also means that we can compute the largest empty circle of a planar point set in quadratic time and constant work-space. As another application, we demonstrate how to enumerate the features of an Euclidean minimum spanning tree (EMST) in quadratic time per step, so that the whole EMST can be found in cubic time using constant work-space. Finally, we describe how to compute a shortest geodesic path between two points in a simple polygon. Although the shortest path problem in general graphs is NL-complete (Jakoby and Tantau 2003), this constrained problem can be solved in quadratic time using only constant work-space., Journal of Computational Geometry, Vol 2, No 1 (2011)

We prove that, for fixed n there exist only finitely many embeddings of Q-factorial toric varieties X into P^n that are induced by a complete linear system. The proof is based on a combinatorial result that for fixed nonnegative integers d and n, there are only finitely many smooth d-polytopes with n lattice points. We also enumerate all smooth 3-polytopes with at most 12 lattice points. In fact, it is sufficient to bound the singularities and the number of lattice points on edges to prove finiteness., Comment: 20+2 pages; major revision: new author, new structure, new results

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant $k$. In particular, we consider triangulations of sets of $n$ points in convex position in the plane and prove that their flip graph is connected if and only if $k > 6$; the diameter of the flip graph is $O(n^2)$. We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for $k \leq 9$, and flip graphs of triangulations can be disconnected for any $k$. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound $k$ by a small constant. Any two triangulations with maximum degree at most $k$ of a convex point set are connected in the flip graph by a path of length $O(n \log n)$, where every intermediate triangulation has maximum degree at most $k+4$., 13 pages, 12 figures, acknowledgments updated

Approximating a given three-dimensional object in order to simplify its handling is a classical topic in computational geometry and related fields. A typical approach is based on incremental approximation algorithms, which start with a small and topologically correct polytope representation (the seed polytope) of a given sample point cloud or input mesh. In addition, a correspondence between the faces of the polytope and the respective regions of the object boundary is needed to guarantee correctness. We construct such a polytope by first computing a simplified though still homotopy equivalent medial axis transform of the input object. Then, we inflate this medial axis to a polytope of small size. Since our approximation maintains topology, the simplified medial axis transform is also useful for skin surfaces and envelope surfaces.

Given points in convex position in three dimensions, we want to find an approximating convex surface consisting of spherical patches, such that all points are within some specified tolerance bound ε of the approximating surface. We describe a greedy algorithm which constructs an approximating surface whose spherical patches are associated to the faces of an inscribed polytope. We show that deciding whether an approximation with not more than a given number of spherical patches exists is NP-hard.

Principle component analysis (PCA) is commonly used to compute a bounding box of a point set in Rd. The popularity of this heuristic lies in its speed, easy implementation and in the fact that usually, PCA bounding boxes quite well approximate the minimum-volume bounding boxes. In this paper we give a lower bound on the approximation factor of PCA bounding boxes of convex polytopes in arbitrary dimension, and an upper bound on the approximation factor of PCA bounding boxes of convex polygons in R2.

We study the problem of shortest paths for a line segment in the plane. As a measure of the distance traversed by a path, we take the average curve length of the orbits of prescribed points on the line segment. This problem is nontrivial even in free space (i.e., in the absence of obstacles). We characterize all shortest paths of the line segment moving in free space under the measure d₂, the average orbit length of the two endpoints. The problem of d₂ optimal motion has been solved by Gurevich and also by Dubovitskij, who calls it Ulam's problem. Unlike previous solutions, our basic tool is Cauchy's surface-area formula. This new approach is relatively elementary, and yields new insights.

Given a set of points in the plane, we want to establish a connection network between these points that consists of several disjoint layers. Motivated by sensor networks, we want that each layer is spanning and plane, and that no edge is very long (when compared to the minimum length needed to obtain a spanning graph). We consider two different approaches: first we show an almost optimal centralized approach to extract two trees. Then we show a constant factor approximation for a distributed model in which each point can compute its adjacencies using only local information. This second approach may create cycles, but maintains planarity.

Tropical geometry is a discrete analogue of algebraic geometry where addition is replaced by taking the minimum (or maximum) and multiplication is replaced by addition. It is an active research eld where tropical analogues of geometric concepts, like linear spaces, varieties, polytopes or volume, are in different stages of development. The interest of these analogues is twofold: their combinatorial nature helps us understand difficult geometric objects and develop algorithms for them, and at the same time they bring geometric language to the field of mathematical optimization. The application of tropical geometry to linear programming has been introduced in [5], where tropical ideas were used to prove that log-barrier interior point linear programming algorithms, known to run in weakly polynomial time, cannot run in strongly polynomial time. In a similar spirit, we are interested in the study of the tropical distance and in particular how it relates to existing tropical linear programming algorithms. The problem of algorithmically solving tropical linear programs is particularly interesting because it lies in the classes of NP and co-NP problems, but no polynomial time algorithm for it is known yet. The problem has an interpretation in the context of metric tropical geometry, but it is still unknown how to use this geometric information for tropical linear feasibility algorihtms. For this reason we introduce here the study of tropical bisectors and Voronoi diagrams, as well as algorithms for their computation.Even though our study focuses on these objects on their own, they will be necessary for understanding tropical analogues for the ellipsoid method or the Kaczmarz iteration algorithm. It is relevant to develop such analogues, because both of these algorithms run in (weakly) polynomial time for classical linear programming. The rest of the thesis looks at the diameter of simplicial complexes, a combinatorial generalization of polytopes. Both classical and tropical simplex methods for linear programming involve exploring the dual graph of some simplicial sphere. Thus, studying the diameter of such complexes is relevant for the understanding of the simplex method's computational complexity. We present new constructions for abstract simplicial complexes with asymptotically large diameter, close to the theoretical upper bound, using a probabilistic construction. We also construct small simplicial spheres with large diameter using a computational heuristic approach, and we develop the topological analogue of the prismatoids used by Santos to disprove the Hirsch conjecture. Tropische Geometrie ist ein diskretes Analogon zu algebraischer Geometrie, bei dem Addition durch Minimumsbildung (oder Maximumsbildung) und Multiplikation durch Addition ersetzt wird. Sie ist ein aktives Forschungsfeld; tropische Analoga zu geometrischen Konzepten wie Volumina, Polytopen, linearen Räumen oder Varietäten sind in unterschiedlichen Stadien der Entwicklung. Diese Analoga sind in zweierlei Hinsicht interessant: Zum einen hilft uns ihre kombinatorische Natur, komplizierte geometrische Objekte zu verstehen und Algorithmen für sie zu entwickeln. Zum anderen ermöglichen sie die Verwendung geometrischer Sprache für mathematische Optimierung. Anwendungen tropischer Geometrie auf lineare Programmierung wurden erstmals in [5] untersucht. Dort werden tropische Ideen verwendet, um zu beweisen, dass Innere-Punkte-Methoden mit logarithmischer Barrier-Funktion, die bekanntermaÿen in schwach polynomineller Zeit terminieren, nicht in stark polynomineller Zeit terminieren können. Diesem Ansatz folgend untersuchen wir hier die tropische Abstandsfunktion auch im Zusammenhang mit bestehenden Algorithmen zur tropischen linearen Programmierung. Das Problem der algorithmischen Lösung tropischer linearer Programme ist besonders interessant, da es im Schnitt der Klassen NP und Co-NP liegt, aber noch kein Lösungsalgorithmus mit polynomineller Laufzeit bekannt ist. Es lässt sich im Kontext metrischer tropischer Geometrie interpretieren; bisher ist allerdings unklar, wie sich diese geometrische Information in Algorithmen zur Bestimmung der Lösbarkeit tropischer linearer Programme einbinden lässt. Aus diesem Grund stellen wir hier eine Untersuchung von tropischen Voronoi-Diagrammen, tropischen Bisektoren und Algorithmen zu ihrer Berechnung vor. Unsere Arbeit legt den Fokus auf die Untersuchung dieser Objekte an sich; sie werden aber auch für das Verständnis tropischer Analoga zur Ellipsoidmethode oder zur Kaczmarz-Methode notwendig sein. Die Entwicklung solcher Analoga ist relevant, da beide Algorithmen für klassische lineare Programme (schwach) polynominelle Laufzeit aufweisen. Der Rest der Arbeit befasst sich mit dem Durchmesser von Simplizialkomplexen, einer kombinatorischen Verallgemeinerung von Polytopen. Sowohl klassische als auch tropische Simplex-Methoden für lineare Programmierung beinhalten die Untersuchung des dualen Graphen einer simplizialen Sphäre. Die Untersuchung des Durchmessers solcher Komplexe ist daher für das Verständnis der Komplexität dieser Methoden relevant. Wir präsentieren neue Konstruktionen abstrakter Simplizialkomplexe mit asymptotisch groÿem Durchmesser nahe an der theoretischen oberen Schranke, unter Verwendung einer probabilistischen Konstruktion. Wir konstruieren weiterhin, mithilfe eines heuristischen Ansatzes, kleine simpliziale Sphären mit groÿem Durchmesser, und entwickeln das topologische Analogon zu den Prismatoiden, die Santos verwendet um die Hirsch-Vermutung zu widerlegen.

In this dissertation we investigate some problems from the field of combinatorics and computational geometry which involve basic geometric entities (points, lines, and circles). In the first part we look at Erdös-Szekeres type problems: The classical theorem by Erdös and Szekeres from 1935 asserts that, for every natural number 𝑘, every sufficiently large point set in general position contains a subset of 𝑘 points in convex position - a so called "𝑘-gon". We will investigate the famous variant of "𝑘-holes", which are 𝑘-gons with the additional property that no other point lies in the convex hull of the 𝑘-hole. This variant differs from the original setting as there exist arbitrarily large point sets which do not contain 7-holes. Besides the existence of holes, also the number of 𝑘-holes in sets of 𝑛 points have been studied intensively. It is well-known that point configurations contain at least quadratically many 3- and 4-holes, respectively, while point configurations with only quadratically many holes exist. Concerning 5- and 6-holes, the best published lower bounds were only linear at the time when I started my studies. In this thesis we present the first superlinear lower bound on the number of 5-holes, which is the first asymptotic improvement since Harborth's linear lower bound from 1978. For our proof we combine classical paper-and-pen proofs with lemmas that were proven using heavy computer asstistance. We also develop a framework based on Boolean logic to investigate various combinatorial properties of point sets with the aid of SAT solvers. In the second part we investigate arrangements of circles. Towards a better understanding of their structure and also to get rid of geometric difficulties, we look at the more general setting of "arrangements of pseudocircles" which was first introduced by Grünbaum in the 1970's. An arrangement of pseudocircles is a collection of simple closed curves on the sphere or in the plane such that any two of the curves are either disjoint or intersect in exactly two points, where the two curves cross. In his book, Grünbaum conjectured that every digon-free arrangement of n pairwise intersecting pseudocircles contains at least 2𝑛-4 triangular cells. We present arrangements to disprove this conjecture and give new bounds on the number of triangular cells for various classes of arrangements. Furthermore, we study the "circularizability" of arrangements: it is clear that every arrangement of circles is an arrangement of pseudocircles, however, deciding whether an arrangement of pseudocircles is isomorphic to an arrangement of circles is computationally hard. Using a computer program, we have enumerated all combinatorially different arrangements of up to 7 pseudocircles. For the class of arrangements of 5 pseudocircles and for the class of digon-free intersecting arrangements of 6 pseudocircles, we give a complete classification: we either provide a circle representation or a non-circularizability proof. For these proofs we use incidence theorems like Miquel's and arguments based on continuous deformation, where circles of an assumed circle representation grow or shrink in a controlled way. In the third and last part we summarize the results from Part I and Part II, and discuss further questions. In dieser Dissertation untersuchen wir Probleme aus den Gebieten Kombinatorik und Algorithmische Geometrie auf elementaren geometrischen Entitäten (Punkten, Linien und Kreisen). Im ersten Teil betrachten wir sogenannte "Erdös--Szekeres type problems": Ein klassisches Resultat von Erdös und Szekeres aus dem Jahr 1935 besagt, dass für jede natürliche Zahl 𝑘 jede hinreichend große Punktmenge in allgemeiner Lage eine Teilmenge von 𝑘 Punkten in konvexer Lage enthält - sogenannte "𝑘-Gons". Wir untersuchen eine berühmte Variation: Ein "𝑘-Loch" ist ein 𝑘-Gon mit der zusätzlichen Eigenschaft, dass kein weiterer Punkt in der konvexen Hülle des 𝑘-Lochs liegt. Diese Variante unterscheidet sich vom ursprünglichen Problem da beliebig große Punktmengen ohne 7-Löcher existieren. Neben der Existenz von 𝑘-Löchern wurde auch die Anzahl an 𝑘-Löchern in 𝑛-Punktmengen intensiv untersucht. Jede Punktmenge hat mindestens quadratisch viele 3-Löcher und 4-Löcher, und Punktmengen mit nur quadratisch vielen Löchern existieren. Zu Beginn meines Studiums waren für 5-Löcher und 6-Löcher nur lineare untere Schranken bekannt. In dieser Dissertation präsentieren wir die erste superlineare untere Schranke für die Anzahl an 5-Löchern. Dies ist die erste asymptotische Verbesserung seit Harborths linearer Schranke aus dem Jahr 1978. Für unseren Beweis kombinieren wir traditionelle Beweismethoden mit Lemmas, welche mithilfe von Computerunterstützung verifiziert wurden. Des Weiteren entwickeln wir ein auf Boolescher Aussagenlogik basierendes Framework, welches die Untersuchung diverser kombinatorischer Eigenschaften von Punktmengen mittels SAT-Solver erlaubt. Im zweiten Teil untersuchen wir Arrangements von Kreisen. Um ein besseres Verständnis derer Strukturen zu erhalten und um geometrischen Schwierigkeiten auszuweichen, betrachten wir "Arrangements von Pseudokreisen" - eine Verallgemeinerung von Kreisarrangements, die von Grünbaum in den 1970er Jahren eingeführt wurde. Ein Pseudokreisarrangement ist eine Menge von einfachen geschlossenen Kurven auf der Sphäre oder in der Ebene mit der Eigenschaft, dass je zwei dieser Kurven disjunkt sind oder sich in genau zwei Punkten schneiden. In seinem Buch präsentierte Grünbaum die Vermutung, dass jedes Digon-freie Arrangement von 𝑛 sich paarweise schneidenden Pseudokreisen mindestens 2𝑛-4 Dreieckszellen enthält. Wir präsentieren Arrangements, die diese Vermutung widerlegen und geben neue Schranken für die Anzahl an Dreieckszellen für unterschiedliche Klassen von Arrangements an. Des Weiteren untersuchen wir die "Kreisbarkeit" von Arrangements: Offensichtlich ist jedes Kreisarrangement auch ein Pseudokreisarrangement - es ist jedoch schwer zu entscheiden, ob ein gegebenes Pseudokreisarrangement durch Kreise representiert werden kann. Mit Hilfe eines Computerprogrammes konnten wir alle kombinatorisch unterschiedlichen Arrangements mit bis zu 7 Pseudokreisen enumerieren. Für Arrangements mit 5 Pseudokreisen und für Digon-freie Arrangements von 6 sich paarweise schneidenden Pseudokreisen geben wir eine vollständige Klassifizierung an: Entweder geben wir eine Kreisrepresentation oder einen Nichtkreisbarkeitsbeweis an. Diese Beweise basieren auf Inzidenztheoremen (z.B. dem Satz von Miquel) und Deformations-argumenten, in welchen wir Kreise einer angenommenen Kreisrepresentation in einer kontrollierten Weise ausweiten oder schrumpfen. Im dritten und letzten Teil fassen wir die Ergebnisse aus Teil I und Teil II zusammen, und diskutieren weiterführende Fragen.

This dissertation studies two natural Markov chains, each living on a family of finite distributive lattices and some related results on the enumeration of lattice paths. In the first part of this body of work, we introduce a coupling method – the block coupling technique – and apply it to the k-heights of some families of plane graphs. This gives some insight into the behaviour of the up/down Markov chain on these distributive lattices. Espe- cially it yields some upper bounds to the mixing time of the face flip Markov chain for the sets of 2-heights on some families of graphs, which is bounded by a polynomial in the number of vertices of the graph (and therefor polynomial logarithmic in the size of the state space / set of 2-heights). The second part is accepted for publication by the Journal of Integer Sequences. It focuses on the enumeration of bounded lattice paths and uses transfer matrices and methods from linear algebra to do so. Using these techniques we were able to enumerate a rather general class of lattice paths, which reduce to a lot of different well known integer sequences as special cases, and therefore group them together. Also this method looks promising to enumerate other families of sequences, as it links various fields (Graph Theory, Linear Algebra, and Lattice Path Enumeration) in an easily applicable way. Finally, the third part, considers the distributive lattices of α-orientations on planar graphs and the face flip Markov chain on these sets. It uses tower moves, another coupling method, to show that the the up/down Markov chain is rapid mixing on the set of 2-orientations of planar quadrangulations of maximum degree 4. In addition, this part contains results using the congestion of some carefully chosen families of graphs to prove, that for graphs containing vertices with high degree the Markov chain is not rapid mixing, i.e. that the mixing time can not be bound from above by some polynomial in the logarithm of the size of the state space. Diese Dissertation untersucht zwei natürliche Markov Ketten, die jeweils auf einer Familie endlicher distributiver Verbände leben. Weiterhin enthält sie einige Verwandte Resultate über das Zählen von Gitter-Pfaden. Im ersten Teil der Arbeit stellen wir die Block Coupling Methode vor und wenden sie auf k-heights einiger Familien planarer Graphen an. Dieses gibt etwas Einblick in das Verhalten der up/down-Markov Kette auf diesen distributiven Verbänden. Insbesondere liefern die Untersuchungen einige obere Schranken für die Mischzeit der FaceFlip Markov Kette auf der Menge der 2-heights einiger Graphen-Familien. Wir zeigen dass diese beschränkt ist durch ein Polynom in den Anzahl der Knoten der Graphen (was implizit bedeutet, dass sie polynomiel logarithmisch ist in der Anzahl der 2-heights). Der zweite Teil der Arbeit beschäftigt sich mit dem Zählen beschränkter Gitter-Pfade. Hier werden Transfer Matrizen und Methoden der Linearen Algebra angewendet um diese Pfade zu zählen. Auf diese Art war es möglich, viele bereits bekannte Integer-Sequenzes über die untersuchten beschränkten Gitter-Pfade zu beschreiben und sie daher in einen Zusammenhang zu stellen. Insbesondere scheint diese Methode eine Möglichkeit darzustellen, weitere Familien von Folgen zu untersuchen und sie verbindet einige verschiedene Gebiete der Mathematik. Die Ergebnisse die in diesem Kapitel vorgestellt werden wurden auch vom Journal of Integer Sequences zur Publikation akzeptiert. Der dritte Teil schliesslich beschäftigt sich mit den distributiven Verbänden von Alpha-Orientierungen planarer Graphen und der Face Flip Markov Kette auf diesen. Es werden Tower Movers, eine weitere coupling Methode, genutzt um zu zeigen, dass die up/down Markov Kette für 2-Orientierungen planarer Quadrangulierungen mit maximal Grad 4 schnell mischend ist. Zusätzlich enthält dieser Teil Resultate, die mithilfe sorgfältig konstruierter Graphenfamilien zeigen, dass für Graphen mit hohem Grad nicht erwartet werden kann, dass die untersuchte Markov Kette schnell mischt.

Given a planar graph $G$ and a partition of the neighbors of each vertex $v$ in four sets $UR(v)$, $UL(v)$, $DL(v)$, and $DR(v)$, the problem Windrose Planarity asks to decide whether $G$ admits a windrose-planar drawing, that is, a planar drawing in which (i) each neighbor $u \in UR(v)$ is above and to the right of $v$, (ii) each neighbor $u \in UL(v)$ is above and to the left of $v$, (iii) each neighbor $u \in DL(v)$ is below and to the left of $v$, (iv) each neighbor $u \in DR(v)$ is below and to the right of $v$, and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a given combinatorial embedding. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph with $n$ vertices that has a windrose-planar drawing, we can construct one with at most one bend per edge and with at most $2n-5$ bends in total, which lies on the $3n \times 3n$ grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area., Appeared in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)

In this thesis we develop and analyze algorithms for computing space-filling curve orders, Delaunay Tessellations and flow complexes of point sets. For space-filling curve orders and Delaunay Tessellations the emphasis lies on an average-case analysis of the algorithms. For flow complexes the emphasis lies on their computation in higher dimensions. In a space-filling curve order of a point set, points which are close in the order are also close in space. We discuss algorithms for computing space-filling curve orders based on radix sort. We give an average-case analysis which shows that these orders can be computed in linear expected time for many point distributions. As discrete counterparts of space-filling curves we consider grid traversals and discuss finding optimal grid traversals for different locality measures using heuristics for the quadratic assignment problem. The Delaunay Tessellation of a point set is a simplicial complex capturing proximity relations of the points. We analyze incremental constructions of Delaunay Tessellations along space-filling curve orders. First we give a generalized and refined analysis of incremental constructions con BRIO, i.e., where points are inserted in random rounds. Based on this we analyze incremental constructions along space- filling curve orders for uniformly distributed points from a bounded convex region in the plane, normally distributed points in the plane, and uniformly distributed points from a d-cube in higher dimensions. In the first case we analyze the expected structure of the Delaunay Tessellation and in the other cases the structure of the space-filling curve order. We show for these point distributions that incremental constructions con BRIO of Delaunay Tessellations run in linear expected time using space-filling curve orders. The flow complex of a point set is the collection of stable manifolds of the flow induced by the distance function of the point set. We give an algorithm for computing the flow complex in higher dimensions. The algorithm is based on the Delaunay Tessellation and Voronoi Diagram of the point set and the recursive nature of the flow. Based on this algorithm we give a topological analysis of flow shapes, i.e., the underlying spaces of subcomplexes of the flow complex. In particular we show that flow shapes are homotopy equivalent to the corresponding unions of balls., In dieser Arbeit werden Algorithmen zur Berechnung von Ordnungen entlang raumfüllender Kurven, von Delaunay-Triangulierungen und von Flusskomplexen entworfen und analysiert. Für Ordnungen entlang raumfüllender Kurven und für Delaunay-Triangulierungen liegt der Schwerpunkt auf einer Analyse der Algorithmen im durchschnittlichen Fall. Für Flusskomplexe liegt der Schwerpunkt auf deren Berechnung in höheren Dimensionen. In einer Ordnung entlang einer raumfüllenden Kurve sind Punkte, die nah in der Ordnung sind, auch nah im Raum. Wir diskutieren Algorithmen zur Berechnung solcher Ordnungen basierend auf Radixsort. Wir geben eine Analyse für den durchschnittlichen Fall, in der wir zeigen, dass diese Ordnungen für viele Punktverteilungen in linearer erwarteter Zeit berechnet werden können. Als diskrete Gegenstücke zu raumfüllenden Kurven betrachten wir Indizierungen von Gitterpunkten. Für verschiedene Lokalitätsmaße berechnen wir Indizierungen basierend auf Heuristiken für das quadratische Zuordnungsproblem. Die Delaunay- Triangulierung einer Punktmenge ist ein simplizialer Komplex auf den Punkten, welcher Nachbarschaftsbeziehungen zwischen den Punkten wiedergibt. Wir analysieren die Laufzeit von inkrementellen Konstruktionen von Delaunay- Triangulierungen, bei denen entlang raumfüllender Kurven eingefügt wird. Zunächst geben wir eine verallgemeinerte und verfeinerte Analyse von inkrementellen Konstruktionen con BRIO, also Konstruktionen, bei denen Punkte in zufälligen Runden eingefügt werden. Darauf basierend analysieren wir inkrementelle Konstruktion entlang raumfüllender Kurven für gleichmäßig verteilte Punkte aus einem beschränkten konvexen Gebiet für normalverteilte Punkte in der Ebene und für gleichmäßig verteilte Punkte aus einem d-dimensionalen Würfel in höheren Dimensionen. Im ersten Fall analysieren wir die erwartete Struktur der Delaunay-Triangulierung und in den anderen Fällen die Struktur der Ordnung entlang der raumfüllenden Kurve. Wir zeigen für diese Verteilungen, dass inkrementelle Konstruktionen con BRIO entlang raumfüllender Kurven in linearer erwarteter Zeit laufen. Der Flusskomplex einer Punktmenge ist die Gesamtheit der stabilen Mannigfaltigkeiten des Flusses, der durch die Distanzfunktion der Punktmenge induziert wird. Wir geben einen Algorithmus zur Berechnung des Flusskomplex in höheren Dimensionen an. Dieser beruht auf der Delaunay-Triangulierung, dem Voronoi Diagramm und der rekursiven Natur des Flusses. Basierend auf dem Algorithmus geben wir eine topologische Analyse der unterliegenden Räume von Subkomplexen des Flusskomplex. Wir zeigen, dass ein solcher Raum homotopieäquivalent zu der entsprechenden Vereinigung von Kugeln ist.

We show that if a planar graph $G$ has a plane straight-line drawing in which a subset $S$ of its vertices are collinear, then for any set of points, $X$, in the plane with $|X|=|S|$, there is a plane straight-line drawing of $G$ in which the vertices in $S$ are mapped to the points in $X$. This solves an open problem posed by Ravsky and Verbitsky in 2008. In their terminology, we show that every collinear set is free. This result has applications in graph drawing, including untangling, column planarity, universal point subsets, and partial simultaneous drawings., Comment: 29 pages, 12 figures