Arrangements of Pseudocircles: On Circularizability
- PDF / 1,553,821 Bytes
- 38 Pages / 439.37 x 666.142 pts Page_size
- 34 Downloads / 224 Views
Arrangements of Pseudocircles: On Circularizability Stefan Felsner1
· Manfred Scheucher1
Received: 3 September 2018 / Revised: 28 January 2019 / Accepted: 4 March 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract 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 crossing points. We call an arrangement intersecting if every pair of pseudocircles intersects twice. An arrangement is circularizable if there is a combinatorially equivalent arrangement of circles. In this paper we present the results of the first thorough study of circularizability. We show that there are exactly four noncircularizable arrangements of 5 pseudocircles (one of them was known before). In the set of 2131 digon-free intersecting arrangements of 6 pseudocircles we identify the three non-circularizable examples. We also show non-circularizability of eight additional arrangements of 6 pseudocircles which have a group of symmetries of size at least 4. Most of our non-circularizability proofs depend on incidence theorems like Miquel’s. In other cases we contradict circularizability by considering a continuous deformation where the circles of an assumed circle representation grow or shrink in a controlled way. The claims that we have all non-circularizable arrangements with the given properties are based on a program that generated all arrangements up to a certain size. Given the complete lists of arrangements, we used heuristics to find circle representations. Examples where the heuristics failed were examined by hand.
Dedicated to the memory of Ricky Pollack. Editor in Charge: Kenneth Clarkson Partially supported by the DFG Grants FE 340/11-1 and FE 340/12-1. Manfred Scheucher was partially supported by the ERC Advanced Research Grant No. 267165 (DISCONV). We gratefully acknowledge the computing time granted by TBK Automatisierung und Messtechnik GmbH and by the Institute of Software Technology, Graz University of Technology. We also thank the anonymous reviewers for valuable comments. Stefan Felsner [email protected] Manfred Scheucher [email protected] 1
Institut für Mathematik, Technische Universität Berlin, 10623 Berlin, Germany
123
Discrete & Computational Geometry
1 Introduction Arrangements of pseudocircles generalize arrangements of circles in the same vein as arrangements of pseudolines generalize arrangements of lines. The study of arrangements of pseudolines was initiated by Levi [18] in 1918. Since then arrangements of pseudolines were intensively studied. The handbook article on the topic [8] lists more than 100 references. To the best of our knowledge the study of arrangements of pseudocircles was initiated by Grünbaum [14] in the 1970s. A pseudocircle is a simple closed curve in the plane or on the sphere. An arrangement of pseudocircles is a collection of pseudocircles with the property that the intersection of any two of the pseudocircles is
Data Loading...
