This module gathers everything that has to do with pseudolines, and for a start a PseudolineArrangement class that can be used to describe an arrangement of pseudolines in several different ways, and to translate one description into another, as well as to display Wiring diagrams via the show method.
In the following, we try to stick to the terminology given in [Felsner], which can be checked in case of doubt. And please fix this module’s documentation afterwards :-)
Definition
A pseudoline can not be defined by itself, though it can be thought of as a \(x\)-monotone curve in the plane. A set of pseudolines, however, represents a set of such curves that pairwise intersect exactly once (and hence mimic the behaviour of straight lines in general position). We also assume that those pseudolines are in general position, that is that no three of them cross at the same point.
The present class is made to deal with a combinatorial encoding of a pseudolines arrangement, that is the ordering in which a pseudoline \(l_i\) of an arrangement \(l_0, ..., l_{n-1}\) crosses the \(n-1\) other lines.
Warning
It is assumed through all the methods that the given lines are numbered according to their \(y\)-coordinate on the vertical line \(x=-\infty\). For instance, it is not possible that the first transposition be (0,2) (or equivalently that the first line \(l_0\) crosses is \(l_2\) and conversely), because one of them would have to cross \(l_1\) first.
Permutations
An arrangement of pseudolines can be described by a sequence of \(n\) lists of length \(n-1\), where the \(i\) list is a permutation of \(\{0, ..., n-1\} \backslash i\) representing the ordering in which the \(i\) th pseudoline meets the other ones.
sage: from sage.geometry.pseudolines import PseudolineArrangement
sage: permutations = [[3, 2, 1], [3, 2, 0], [3, 1, 0], [2, 1, 0]]
sage: p = PseudolineArrangement(permutations)
sage: p
Arrangement of pseudolines of size 4
sage: p.show()
Sequence of transpositions
An arrangement of pseudolines can also be described as a sequence of \(\binom n 2\) transpositions (permutations of two elements). In this sequence, the transposition \((2,3)\) appears before \((8, 2)\) iif \(l_2\) crosses \(l_3\) before it crosses \(l_8\). This encoding is easy to obtain by reading the wiring diagram from left to right (see the show method).
sage: from sage.geometry.pseudolines import PseudolineArrangement
sage: transpositions = [(3, 2), (3, 1), (0, 3), (2, 1), (0, 2), (0, 1)]
sage: p = PseudolineArrangement(transpositions)
sage: p
Arrangement of pseudolines of size 4
sage: p.show()
Note that this ordering is not necessarily unique.
Felsner’s Matrix
Felser gave an encoding of an arrangement of pseudolines that takes \(n^2\) bits instead of the \(n^2log(n)\) bits required by the two previous encodings.
Instead of storing the permutation [3, 2, 1] to remember that line \(l_0\) crosses \(l_3\) then \(l_2\) then \(l_1\), it is sufficient to remember the positions for which each line \(l_i\) meets a line \(l_j\) with \(j < i\). As \(l_0\) – the first of the lines – can only meet pseudolines with higher index, we can store [0, 0, 0] instead of [3, 2, 1] stored previously. For \(l_1\)‘s permutation [3, 2, 0] we only need to remember that \(l_1\) first crosses 2 pseudolines of higher index, and then a pseudoline with smaller index, which yields the bit vector [0, 0, 1]. Hence we can transform the list of permutations above into a list of \(n\) bit vectors of length \(n-1\), that is
In order to go back from Felsner’s matrix to an encoding by a sequence of transpositions, it is sufficient to look for occurrences of \(\begin{array}{c}0\\1\end{array}\) in the first column of the matrix, as it corresponds in the wiring diagram to a line going up while the line immediately above it goes down – those two lines cross. Each time such a pattern is found it yields a new transposition, and the matrix can be updated so that this pattern disappears. A more detailed description of this algorithm is given in [Felsner].
sage: from sage.geometry.pseudolines import PseudolineArrangement
sage: felsner_matrix = [[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 1, 1]]
sage: p = PseudolineArrangement(felsner_matrix)
sage: p
Arrangement of pseudolines of size 4
Let us define in the plane several lines \(l_i\) of equation \(y = a x+b\) by picking a coefficient \(a\) and \(b\) for each of them. We make sure that no two of them are parallel by making sure all of the \(a\) chosen are different, and we avoid a common crossing of three lines by adding a random noise to \(b\):
sage: n = 20
sage: l = zip(Subsets(20*n,n).random_element(), [randint(0,20*n)+random() for i in range(n)])
sage: print l[:5] # not tested
[(96, 278.0130613051349), (74, 332.92512282478714), (13, 155.65820951249867), (209, 34.753946221755307), (147, 193.51376457741441)]
sage: l.sort()
We can now compute for each \(i\) the order in which line \(i\) meets the other lines:
sage: permutations = [[0..i-1]+[i+1..n-1] for i in range(n)]
sage: a = lambda x : l[x][0]
sage: b = lambda x : l[x][1]
sage: for i, perm in enumerate(permutations):
....: perm.sort(key = lambda j : (b(j)-b(i))/(a(i)-a(j)))
And finally build the line arrangement:
sage: from sage.geometry.pseudolines import PseudolineArrangement
sage: p = PseudolineArrangement(permutations)
sage: print p
Arrangement of pseudolines of size 20
sage: p.show(figsize=[20,8])
[Felsner] | (1, 2) On the Number of Arrangements of Pseudolines, Stefan Felsner, http://page.math.tu-berlin.de/~felsner/Paper/numarr.pdf |
Nathann Cohen
Creates an arrangement of pseudolines.
INPUT:
seq (a sequence describing the line arrangement). It can be :
- A list of \(n\) permutations of size \(n-1\).
- A list of \(\binom n 2\) transpositions
- A Felsner matrix, given as a sequence of \(n\) binary vectors of length \(n-1\).
encoding (information on how the data should be interpreted), and can assume any value among ‘transpositions’, ‘permutations’, ‘Felsner’ or ‘auto’. In the latter case, the type will be guessed (default behaviour).
Note
TESTS:
From permutations:
sage: from sage.geometry.pseudolines import PseudolineArrangement
sage: permutations = [[3, 2, 1], [3, 2, 0], [3, 1, 0], [2, 1, 0]]
sage: PseudolineArrangement(permutations)
Arrangement of pseudolines of size 4
From transpositions
sage: from sage.geometry.pseudolines import PseudolineArrangement
sage: transpositions = [(3, 2), (3, 1), (0, 3), (2, 1), (0, 2), (0, 1)]
sage: PseudolineArrangement(transpositions)
Arrangement of pseudolines of size 4
From a Felsner matrix:
sage: from sage.geometry.pseudolines import PseudolineArrangement
sage: permutations = [[3, 2, 1], [3, 2, 0], [3, 1, 0], [2, 1, 0]]
sage: p = PseudolineArrangement(permutations)
sage: matrix = p.felsner_matrix()
sage: PseudolineArrangement(matrix) == p
True
TESTS:
Wrong input:
sage: PseudolineArrangement([[5, 2, 1], [3, 2, 0], [3, 1, 0], [2, 1, 0]])
Traceback (most recent call last):
...
ValueError: Are the lines really numbered from 0 to n-1?
sage: PseudolineArrangement([(3, 2), (3, 1), (0, 3), (2, 1), (0, 2)])
Traceback (most recent call last):
...
ValueError: A line is numbered 3 but the number of transpositions ...
Returns a Felsner matrix describing the arrangement.
See the pseudolines module‘s documentation for more information on this encoding.
EXAMPLE:
sage: from sage.geometry.pseudolines import PseudolineArrangement
sage: permutations = [[3, 2, 1], [3, 2, 0], [3, 1, 0], [2, 1, 0]]
sage: p = PseudolineArrangement(permutations)
sage: p.felsner_matrix()
[[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 1, 1]]
Returns the arrangements as \(n\) permutations of size \(n-1\).
See the pseudolines module‘s documentation for more information on this encoding.
EXAMPLE:
sage: from sage.geometry.pseudolines import PseudolineArrangement
sage: permutations = [[3, 2, 1], [3, 2, 0], [3, 1, 0], [2, 1, 0]]
sage: p = PseudolineArrangement(permutations)
sage: p.permutations()
[[3, 2, 1], [3, 2, 0], [3, 1, 0], [2, 1, 0]]
Displays the pseudoline arrangement as a wiring diagram.
INPUT:
EXAMPLE:
sage: from sage.geometry.pseudolines import PseudolineArrangement
sage: permutations = [[3, 2, 1], [3, 2, 0], [3, 1, 0], [2, 1, 0]]
sage: p = PseudolineArrangement(permutations)
sage: p.show(figsize=[7,5])
TESTS:
sage: from sage.geometry.pseudolines import PseudolineArrangement
sage: permutations = [[3, 2, 1], [3, 2, 0], [3, 0, 1], [2, 0, 1]]
sage: p = PseudolineArrangement(permutations)
sage: p.show()
Traceback (most recent call last):
...
ValueError: There has been a problem while plotting the figure...
Returns the arrangement as \(\binom n 2\) transpositions.
See the pseudolines module‘s documentation for more information on this encoding.
EXAMPLE:
sage: from sage.geometry.pseudolines import PseudolineArrangement
sage: permutations = [[3, 2, 1], [3, 2, 0], [3, 1, 0], [2, 1, 0]]
sage: p1 = PseudolineArrangement(permutations)
sage: transpositions = [(3, 2), (3, 1), (0, 3), (2, 1), (0, 2), (0, 1)]
sage: p2 = PseudolineArrangement(transpositions)
sage: p1 == p2
True
sage: p1.transpositions()
[(3, 2), (3, 1), (0, 3), (2, 1), (0, 2), (0, 1)]
sage: p2.transpositions()
[(3, 2), (3, 1), (0, 3), (2, 1), (0, 2), (0, 1)]