Coding and Counting Arrangements of Pseudolines

摘要

Arrangements of lines and pseudolines are important and appealing objects for research in discrete and computational geometry. We show that there are at most simple arrangements of n pseudolines in the plane. This improves on previous work by Knuth who proved an upper bound of in 1992 and the first author, who obtained in 1997. The argument uses surprisingly little geometry. The main ingredient is a lemma that was already central to the argument given by Knuth.