Sweeps, Arrangements and Signotopes

Stefan Felsner
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin
email: felsner@inf.fu-berlin.de

Helmut Weil
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin, Germany
email: weil@inf.fu-berlin.de

Report B 98-06
April 1998

Sweeping is an important algorithmic tool in geometry. In the first part of this paper we define sweeps of arrangements and use the `Sweeping Lemma' to show that Euclidean arrangements of pseudolines can be represented by wiring diagrams and zonotopal tilings.
In the second part we introduce a new representation for Euclidean arrangements of pseudolines. This representation records an `orientation' for each triple of lines. It turns out that a `triple orientation' corresponds to an arrangement exactly if it obeys a generalized transivity law. Moreover, the `triple orientations' carry a natural order relation which induces an order relation on arrangements. A closer look on the combinatorics behind this leads to a series of signotope orders closely related to higher Bruhat orders. We investigate the structure of higher Bruhat orders and give new purely combinatorial proofs for the main structural properties. We answer a question of Ziegler and show that two orderings of the higher Bruhat order B(n,2) coincide. Finally, we reconnect the combinatorics of the second part to geometry. In particular we show that maximum chains in the higher Bruhat orders correspond to sweeps.

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-98-06.ps.gz