Points, lines, and circles:
Manfred Scheucher · DepositOnce · 2020
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.