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.