Publication at Faculty of Mathematics and Physics |
2011
Abstract
Arrangements of lines and pseudolines are important and appealing objects for research in discrete and computational geometry. We show that there are at most 2(0.657n2) simple arrangements of n pseudolines in the plane.
This improves on previous work by Knuth who proved an upper bound of 3((n2)) congruent to 2(0.792 n2) in 1992 and the first author, who obtained 2(0.697n2) in 1997. The argument uses surprisingly little geometry.
The main ingredient is a lemma that was already central to the argument given by Knuth.