# 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 2*n*/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