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()                                                                      # needs sage.plot

>>> from sage.all import *
>>> from sage.geometry.pseudolines import PseudolineArrangement
>>> permutations = [[Integer(3), Integer(2), Integer(1)], [Integer(3), Integer(2), Integer(0)], [Integer(3), Integer(1), Integer(0)], [Integer(2), Integer(1), Integer(0)]]
>>> p = PseudolineArrangement(permutations)
>>> p
Arrangement of pseudolines of size 4
>>> p.show()                                                                      # needs sage.plot

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()                                                                      # needs sage.plot

>>> from sage.all import *
>>> from sage.geometry.pseudolines import PseudolineArrangement
>>> transpositions = [(Integer(3), Integer(2)), (Integer(3), Integer(1)), (Integer(0), Integer(3)), (Integer(2), Integer(1)), (Integer(0), Integer(2)), (Integer(0), Integer(1))]
>>> p = PseudolineArrangement(transpositions)
>>> p
Arrangement of pseudolines of size 4
>>> p.show()                                                                      # needs sage.plot

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^2\log(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

\[\begin{split}\begin{array}{ccc} 3 & 2 & 1\\ 3 & 2 & 0\\ 3 & 1 & 0\\ 2 & 1 & 0\\ \end{array} \Rightarrow \begin{array}{ccc} 0 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 1\\ 1 & 1 & 1\\ \end{array}\end{split}\]

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

>>> from sage.all import *
>>> from sage.geometry.pseudolines import PseudolineArrangement
>>> felsner_matrix = [[Integer(0), Integer(0), Integer(0)], [Integer(0), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(1)], [Integer(1), Integer(1), Integer(1)]]
>>> p = PseudolineArrangement(felsner_matrix)
>>> 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                            # needs sage.combinat
[(96, 278.0130613051349), (74, 332.92512282478714), (13, 155.65820951249867),
 (209, 34.753946221755307), (147, 193.51376457741441)]

>>> from sage.all import *
>>> n = Integer(20)
>>> l = sorted(zip(Subsets(Integer(20)*n, n).random_element(),
...                [randint(Integer(0), Integer(20)*n) + random() for i in range(n)]))
>>> print(l[:Integer(5)])                          # not tested                            # needs sage.combinat
[(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: def a(x): return l[x][0]
sage: def b(x): return l[x][1]
sage: for i, perm in enumerate(permutations):
....:     perm.sort(key=lambda j: (b(j)-b(i))/(a(i)-a(j)))

>>> from sage.all import *
>>> permutations = [(ellipsis_range(Integer(0),Ellipsis,i-Integer(1))) + (ellipsis_range(i+Integer(1),Ellipsis,n-Integer(1))) for i in range(n)]
>>> def a(x): return l[x][Integer(0)]
>>> def b(x): return l[x][Integer(1)]
>>> 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])                                                        # needs sage.combinat sage.plot

>>> from sage.all import *
>>> from sage.geometry.pseudolines import PseudolineArrangement
>>> p = PseudolineArrangement(permutations)
>>> print(p)
Arrangement of pseudolines of size 20
>>> p.show(figsize=[Integer(20),Integer(8)])                                                        # needs sage.combinat sage.plot

Author

Nathann Cohen

Methods

class sage.geometry.pseudolines.PseudolineArrangement(seq, encoding='auto')[source]

Bases: object

Create 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,\dots,n-1\).

  • For more information on the different encodings, see the pseudolines module’s documentation.

felsner_matrix()[source]

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]]

>>> from sage.all import *
>>> from sage.geometry.pseudolines import PseudolineArrangement
>>> permutations = [[Integer(3), Integer(2), Integer(1)], [Integer(3), Integer(2), Integer(0)], [Integer(3), Integer(1), Integer(0)], [Integer(2), Integer(1), Integer(0)]]
>>> p = PseudolineArrangement(permutations)
>>> p.felsner_matrix()
[[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 1, 1]]
permutations()[source]

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]]

>>> from sage.all import *
>>> from sage.geometry.pseudolines import PseudolineArrangement
>>> permutations = [[Integer(3), Integer(2), Integer(1)], [Integer(3), Integer(2), Integer(0)], [Integer(3), Integer(1), Integer(0)], [Integer(2), Integer(1), Integer(0)]]
>>> p = PseudolineArrangement(permutations)
>>> p.permutations()
[[3, 2, 1], [3, 2, 0], [3, 1, 0], [2, 1, 0]]
show(**args)[source]

Displays the pseudoline arrangement as a wiring diagram.

INPUT:

  • **args – any arguments to be forwarded to the show method. In particular, to tune the dimensions, use the figsize argument (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])                                                 # needs sage.plot

>>> from sage.all import *
>>> from sage.geometry.pseudolines import PseudolineArrangement
>>> permutations = [[Integer(3), Integer(2), Integer(1)], [Integer(3), Integer(2), Integer(0)], [Integer(3), Integer(1), Integer(0)], [Integer(2), Integer(1), Integer(0)]]
>>> p = PseudolineArrangement(permutations)
>>> p.show(figsize=[Integer(7),Integer(5)])                                                 # needs sage.plot
transpositions()[source]

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)]

>>> from sage.all import *
>>> from sage.geometry.pseudolines import PseudolineArrangement
>>> permutations = [[Integer(3), Integer(2), Integer(1)], [Integer(3), Integer(2), Integer(0)], [Integer(3), Integer(1), Integer(0)], [Integer(2), Integer(1), Integer(0)]]
>>> p1 = PseudolineArrangement(permutations)
>>> transpositions = [(Integer(3), Integer(2)), (Integer(3), Integer(1)), (Integer(0), Integer(3)), (Integer(2), Integer(1)), (Integer(0), Integer(2)), (Integer(0), Integer(1))]
>>> p2 = PseudolineArrangement(transpositions)
>>> p1 == p2
True
>>> p1.transpositions()
[(3, 2), (3, 1), (0, 3), (2, 1), (0, 2), (0, 1)]
>>> p2.transpositions()
[(3, 2), (3, 1), (0, 3), (2, 1), (0, 2), (0, 1)]