Kliem, Jonathan
[Verfasser:in]
;
male
[Mitwirkende:r];
Frick, Florian
[Mitwirkende:r];
Stump, Christian
[Mitwirkende:r];
Welker, Volkmar
[Mitwirkende:r]
Applications of Topology, Combinatorics and Algorithms to Discrete Geometry
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
In Chapter 1, we show upper bounds to the Grünbaum–Hadwiger–Ramos problem. We give new proofs for almost all known upper bounds and improve the following cases: Let d,n,k be natural number with d >= 2^n(1 + 2^(k-1)). For any 2^(n+1) masses on R^d there are k affine hyperplanes that induce a partition of R^d into 2^k pieces of equal size w.r.t. all masses. In Chapter 2, we use similar methods for a similar problem. k hyperplanes split R^d into up to 2^k non-empty chambers. Similar to a chess board we color the chambers with black and white. Given 2^a(2h + 1) + l masses in R^(2^a + l). We show that there exist 2h + 1 hyperplanes that that split into a black and a white part of equal size w.r.t. to all masses. In Chapter 3, we discuss a new memory-efficient depth-first algorithm and its implementation that iterates over all elements of a finite locally branched lattice. This algorithm can be applied to face lattices of polyhedra and to various generalizations such as finite polyhedral complexes and subdivisions of manifolds, extended tight spans and closed sets of matroids. Its practical implementation is very fast compared to state-of-the-art implementations of previously considered algorithms. Based on recent work of Bruns, García-Sánchez, O’Neill and Wilburne, we apply this algorithm to prove Wilf ’s conjecture for all numerical semigroups of multiplicity 19 by iterating through the faces of the Kunz cone and identifying the possible bad faces and then checking that these do not yield counterexamples to Wilf’s conjecture. In Chapter 4, we provide an algorithm that verifies the optimal colored Tverberg problem for 10 points in the plane: Every 10 points in the plane in color classes of size at most 3 can be partitioned in 4 rainbow pieces such that their convex hulls intersect in a common point. This is achieved by translating the problem to k-partite graphs and using a new algorithm to verify that those graphs do not have a k-clique. ; In Kapitel 1 zeigen wir obere Schranken des ...