Pseudolines¶
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 [Fe1997], 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.
Encodings¶
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 [Fe1997].
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
Example¶
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 = sorted(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)]
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])
Author¶
Nathann Cohen
Methods¶
-
class
sage.geometry.pseudolines.PseudolineArrangement(seq, encoding='auto')¶ 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
- The pseudolines are assumed to be integers \(0..(n-1)\).
- For more information on the different encodings, see the
pseudolines module’s documentation.
-
felsner_matrix()¶ Return a Felsner matrix describing the arrangement.
See the
pseudolines module’s documentation for more information on this encoding.EXAMPLES:
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]]
-
permutations()¶ Return the arrangements as \(n\) permutations of size \(n-1\).
See the
pseudolines module’s documentation for more information on this encoding.EXAMPLES:
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]]
-
show(**args)¶ Displays the pseudoline arrangement as a wiring diagram.
INPUT:
**args– any arguments to be forwarded to theshowmethod. In particular, to tune the dimensions, use thefigsizeargument (example below).
EXAMPLES:
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])
-
transpositions()¶ Return the arrangement as \(\binom n 2\) transpositions.
See the
pseudolines module’s documentation for more information on this encoding.EXAMPLES:
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)]