On the Number of Arrangements of Pseudolines

Stefan Felsner

Institut für Informatik
Freie Universität Berlin
email: felsner@inf.fu-berlin.de
Report B 95-20
December 1995

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-95-20.ps.gz
On the Number of Arrangements of Pseudolines Given a simple arrangement of n pseudolines in the Euclidean plane, associate with line i the list \sigma_i of the lines crossing i in the order of the crossings on line i. \sigma_i=(\sigma^i_1,\sigma^i_2,..,\sigma^i_{n-1}) is a permutation of \{1,..,n\} - \{i\}. The vector (\sigma_1,\sigma_2,\ldots,\sigma_n) is an encoding for the arrangement. Define \tau^i_j = 1 if \sigma^i_j > i and \tau^i_j = 0, otherwise. Let \tau_i=(\tau^i_1,\tau^i_2,..,\tau^i_{n-1}), we show that the vector (\tau_1,\tau_2,\ldots,\tau_n) is already an encoding.

We use this encoding to improve the upper bound on the number of arrangements of n pseudolines to 2^{0.6988\cdot n^2}. Moreover, we have enumerated arrangements with 10 pseudolines. As a by-product we determine their exact number and we can show that the maximal number of halving lines of 10 point in the plane is 13.