Triangles in Euclidean Arrangements

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

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

Report B 97-09
November 1997

The number of triangles in arrangements of lines and pseudolines has been object of some research. Most results, however, concern arrangements in the projective plane. In this article we add results for the number of triangles in Euclidean arrangements of pseudolines. Though the change in the embedding space from projective to Euclidean may seem small there are interesting changes both in the results and in the techniques required for the proofs.
In 1926 Levi proved that a nontrivial arrangement - simple or not - of n pseudolines in the projective plane contains n triangles. To show the corresponding result for the Euclidean plane, namely, that a simple arrangement of n pseudolines contains n -2 triangles, we had to find a completely different proof. On the other hand a non-simple arrangements of n pseudolines in the Euclidean plane can have as few as 2n/3 triangles and this bound is best possible. We also discuss the maximal possible number of triangles and some extensions.

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