Triangles in Euclidean Arrangements

Stefan Felsner and Klaus Kriegel

Freie Universität Berlin
Fachbereich Mathematik und Informatik
Takustr. 9, 14195 Berlin, Germany
{felsner,kriegel}@inf.fu-berlin.de

Abstract. The number of triangles in arrangements of lines and pseudo-

lines has been object of some research. Most results, however, concern
arrangements in the projective plane. We obtain 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 cor-
responding result for the Euclidean plane, namely, that a simple arrange-
ment of n pseudolines contains n − 2 triangles, we had to find a com-
pletely 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.

Mathematics Subject Classifications (1991). 52A10, 52C10.

Key Words. Arrangement, Euclidean plane, pseudoline, strechability,

triangle.

1 Introduction, Definitions and Overview

A natural approach to generate an object from a combinatorial class at

random is to set up an appropriate Markov chain. Basically this works as
follows: The objects in the class are the vertex set of a so called transi-
tion graph. The (directed) edges in this graph are defined by some local
operations which transform one object into another one.
For arrangements of pseudolines a natural choice for the local opera-
tions are triangular flips. The mixing rate of the Markov chain depends on
the expansion properties of the transition graph. A necessary condition
for good expansion is a sufficiently large degree. In the setting described
J. Hromkovič, O. Sýkora (Eds.): WG’98, LNCS 1517, pp. 137–148, 1998.

c Springer-Verlag Berlin Heidelberg 1998
138 S. Felsner and K. Kriegel

the degree of a vertex, i.e., an arrangement A, is the number p3 (A) of tri-

angles of the arrangement. In this article we show some results concerning
the number of triangles in Euclidean arrangements of pseudolines.
Grünbaum [4] defines an arrangement A of lines as a finite collection
{L0 , L1 , . . . , Ln } of lines, i.e., 1–dimensional subspaces in the real projec-
tive plane IP. Specifying a line L0 in A as the “line at infinity” induces the
arrangement AL0 of lines {L1 , . . . , Ln } in the Euclidean plane IE = IP\L0 .
With an arrangement we associate the cell complex of vertices edges
and cells into which the lines of the arrangement decompose the under-
lying space IP or IE. Arrangements are isomorphic provided their cell
complexes are isomorphic.
An arrangement B of pseudolines in IP is a collection {P0 , P1 , . . . , Pn }
of simple closed curves (we call them pseudolines) in IP such that every
two curves have exactly one point in common. Specifying a pseudoline P0
in B as the line at infinity induces the arrangement BP0 of pseudolines
{P1 , . . . , Pn } in IP \ P0 . Since IP \ P0 is homeomorphic to the Euclidean
plane and we are interested in properties of the induced cell complex we
may regard BP0 as an arrangement in IE.
Already in early work of Levi [7] and Ringel [8] it has been noted that
arrangements of pseudolines are a proper generalization of arrangements
of lines. This is due to the existence of incidence laws in plane geometry
,e.g., the Theorem of Pappus. Arrangements of pseudolines have gained
attention since they provide a generic model for oriented matroids of rank
3. In this context questions of strechability have attained considerable
interest. For more about these connections we refer the reader to the
‘bible of oriented matroids’ [1].
An arrangement is called trivial if all the (pseudo)lines intersect in a
single point. If no point belongs to more then two of the (pseudo)lines we
call the arrangement simple.
Euclidean arrangements of pseudolines will be the main object of in-
vestigations in this paper. Work with these objects is simplified by the
fact that every arrangement of pseudolines, i.e., of doubly unbounded
curves, is isomorphic to an arrangement of x-monotone pseudolines, i.e.,
of curves that intersect every vertical line in exactly one point. Particu-
larly nice pictures of Euclidean arrangements of pseudolines are given by
their wiring diagrams introduced in Goodman [3], see Figure 1. In this
representation the n x-monotone curves are restricted to n y-coordinates
except for some local switches where adjacent lines cross. Knuth [6] points
out a connection with ‘primitive sorting networks’.
 Triangles in Euclidean Arrangements 139

5 1
4 2
3 3
2 4
1 5
Figure 1. Wiring diagram of a simple arrangement of 5 pseudolines.

We now summarize bounds for the number p3 of triangles in arrange-

ments.
Theorem 1. For every arrangement A of n pseudolines in IP:
(1) Every pseudoline is incident with at least three triangles. Since every
triangle is incident with three lines this implies p3 ≥ n.
(2) p3 ≤ 13 n(n − 1) for n ≥ 10 with equality for infinitely many values
of n.
Part (1) is due to Levi [7]. The lower bound for p3 it best possible.
To see this take the n supporting lines of the edges of a regular n-gon for
n ≥ 4. The arrangement thus obtained is a simple arrangement of lines
with p3 = n.
Part (2) has a more entangled history. In [4] the following easy ar-
gument for p3 ≤ 13 n(n − 1) in simple arrangements is found. If A is
simple then only one of the cells bounded by an edge can be a trian-
gle. Since there are n(n − 1) edges and every triangle uses three of them
the bound is established. Grünbaums conjectured the same bound for
nonsimple arrangements of lines with sufficiently large n. Several special
cases and lower bounds where proved by Strommer, Purdy and others.
Finally Roudneff [11] proved the conjectured bound for n ≥ 10. By per-
turbing high degree vertices so that suitable arrangements are formed in
the neighborhood he shows that p3 is maximized by what he calls ‘re-
duced arrangements’. In particular these arrangements have no vertices
of degree more then four. The crucial part of the proof is to show that if
ti counts vertices of degree i then for n ≥ 9 every reduced arrangement
has
3p3 ≤ 2(t2 + 3t3 + 6t4 ).

k  n
Since k 2 tk = 2 this implies the bound.
Infinite families of simple arrangements with p3 = 13 n(n−1) have been
obtained by Roudneff [9] and Harborth [5]. For stretchable arrangements
the best known constructions are due to Füredi and Palásti [2]. Their
examples have at least 13 n(n − 3) triangles.
140 S. Felsner and K. Kriegel

In this paper we discuss triangles in Euclidean arrangements. The

cell complex of an arrangement in IE consists of unbounded and bounded
cells. In our treatment we ignore unbounded cells. In the arrangement of
Figure 1 we thus count 3 triangles and 3 quadrangles. Our main results
are summarized in the following Theorem whose proof will be given in
sections 2 and 3.
Theorem 2. For every arrangement B of n pseudolines in IE:
(1) If B is simple then p3 ≥ n − 2.
(2) If n ≥ 6 then p3 ≥ 23 n with equality for all n = 0 (mod 3).
(3) p3 ≤ 13 n(n − 2) with equality for infinitely many values of n.
Part (1) again has a long history. Roberts 1889 claimed that for every
simple arrangement A of n + 1 lines in IP and every line L of A there
are n − 2 triangles not incident with L. The argument however was con-
sidered non-convincing. Ninety years later Shannon [12] proved Roberts
theorem, actually, he proved the analog of Roberts theorem for arbitrary
dimensions. In particular this implies that every stretchable arrangement
B of n lines in IE has at least n − 2 triangles. Add the line at infinity to
obtain a projective arrangement and apply Roberts theorem.
Shannon’s proof does not require that the arrangement is simple.
Therefore, Shannon’s theorem together with Theorem 2 (2) gives the
following amazing result.
Corollary 1. The count of triangles can be a certificate for nonstrecha-
bility of nonsimple Euclidean arrangements.
A similar effect in the projective setting was conjectured by Grünbaum
and proved by Roudneff [10]. A nonsimple projective arrangement with
p3 = n is nonstrechable. An Example of such an arrangement is due to
Canham, see Grünbaum [4, page 55]. In Section 3 we describe a family Wn
of arrangements with few triangles. If Wn is considered as an arrangement
in the projective plane it is a nonsimple arrangement with n lines and
p3 = n.
It is interesting to note that Levi’s theorem about the number of
triangles incident to a line and Roberts respectively Shannons theorem
about the number of triangles avoiding a line both give easy double-
counting proofs for p3 ≥ n. We elaborate the second:
Corollary 2. The number of triangles in a simple arrangement A of n
pseudolines in IP is at least n.
 Triangles in Euclidean Arrangements 141

Proof. For each pseudoline Pi consider the Euclidean arrangement APi

obtained by taking Pi as line at infinity. Each such arrangement has at
least (n − 1) − 2 triangles. Altogether this gives at least n(n − 3) triangles.
Any fixed triangle ∆ in A is bounded by three pseudolines and hence
counted exactly n − 3 times. This shows that there are at least n different
triangles.
The upper bound on the number of triangles in the Euclidean case
claimed in (3) of Theorem 2 can be proved along the lines of Roudneff’s
upper bound for the projective case. The proof is long and the changes
necessary for to adopt it to the Euclidean case obvious. Therefore, we will
refrain from elaborating on it and refer to Roudneff’s original paper [11].
To show that the bound is best possible again the examples from the
same paper [11] do the work. Roudneff shows that there is an infinite
family of simple projective arrangements with n + 1 lines and (n + 1)n/3
triangles. Each line of such an arrangement is incident to n triangles.
Choose an arbitrary line l as line in infinity. The remaining Euclidean
arrangement of n lines has (n + 1)n/3 − n = n(n − 2)/3 triangles.

2 Simple Euclidean Arrangements

In this section we prove the lower bound for the number of triangles in
simple arrangements in IE.

Proposition 1. p3 ≥ n − 2 for every simple arrangement B of n pseudo-

lines in IE.

Proof. We consider the finite part of B as a planar graph. Let V be the

number of vertices E be the number of edges and F be the number of
(finite!) faces. These statistics can all be expressed as functions of the
number of pseudolines.
   
n n−1
V = , E = n (n − 2), F =
2 2

Note that in this setting Euler’s formula gives V − E + F = 1.

We assign labels ⊕ or  to each side of every edge. Let f be one
of the two (possibly unbounded) faces bounded by e and let e and e
be the edge-neighbors of e along f . Let l, l and l be the supporting
pseudolines of e, e and e respectively. The label of e on the side of f is
⊕ if f is contained in the finite triangle T of the arrangement {l, l , l }
otherwise the label is  . See Figure 2 for an illustration of the definition
142 S. Felsner and K. Kriegel

and Figure 3 for a complete labeling. With the next lemmas we collect
important properties of the edge labeling.

e
f

Figure 2. The label of e at f is ⊕ since f is contained in the shaded

triangle.


⊕
⊕
⊕ 
 
⊕

  
⊕
⊕  ⊕⊕ 
⊕ ⊕
⊕
 
 ⊕ ⊕
 ⊕ ⊕ 


Figure 3. The arrangement of Figure 2 with the completed edge labeling.

Lemma 1. Every edge e of a simple arrangement has a ⊕ and a  label.

Proof. Let f1 and f2 be the two faces bounded by e and let e1 , e1 and e2 ,
e2 be the edge-neighbors of e in these two faces. Since the arrangement
is simple the supporting lines {l1 , l1 } of both pairs of edges are the same.
The finite triangular region T of the arrangement {l, l , l } has edge e
on its boundary. Therefore, exactly one of the two faces f1 and f2 is
contained in T . 
 Triangles in Euclidean Arrangements 143

As seen in the proof of the lemma the triangular region T used to define
the edge label of e on the side of f is independent of f . This allows to
adopt the notation T (e) for this region.
Lemma 2. All three edge labels in a triangle are ⊕ . A quadrangle con-
tains two ⊕ and two  labels. For k ≥ 5 a k sided face contains at most
two ⊕ labels.
Proof. If f is a triangle then for each of its edges e the triangular region
T (e) is f itself.
Let f be a quadrangle and e, e be a pair of opposite edges of f . Both
edges have the same neighboring edges, hence, two of the lines bounding
the triangles T (e) and T (e) are equal. It is easy to see that either T (e) =
f ∪ T (e) or T (e) = f ∪ T (e). In the first case e has label ⊕ and e has
label  in the second case the labels are exchanged. The second pair of
opposite edges also has one label ⊕ and the other  .
Let f be a face with k ≥ 5 sides the lemma immediately follows from
the following
Claim. Any two edges with label ⊕ in f are neighbors, i.e., share a com-
mon vertex.
Let e1 , e2 , . . . , ek be the edges of f numbered in counterclockwise di-
rection along f and let li be the supporting line of ei . Let e1 have label ⊕
and consider an edge ei with 3 ≤ i ≤ k − 1. We will show that the label
of ei is  . The argument as given applies to the case 4 ≤ i ≤ k − 1, the
remaining case situation i = 3, however is symmetric to i = k − 1.
Face f is contained in T (e1 ) and line li has to leave T (e1 ) \ f through
lk and l2 . Figure 4 is a generic sketch of the situation.
li

l2 R1

R2
ei
e2

e1
lk

Figure 4. Edge e1 has label ⊕ in f so ei must have .

144 S. Felsner and K. Kriegel

Consider line li−1 . This line enters the region R1 bounded by l2 , li and
the chain of edges e3 , e4 , . . . , ei−1 at the vertex ei−1 ∩ei . To leave region R1
line li−1 has to cross l2 . Therefore, li−1 has to leave the region R2 bounded
by li , l2 and lk through lk . Symmetrically, li+1 has a crossing with lk to
leave the region bounded by lk , li and the chain of edges ei+1 , ei+2 , . . . , ek .
Therefore, to leave region R2 line li+1 has to cross l2 . This shows that
li−1 and li+1 cross inside region R2 . Hence, T (ei ) is contained in R2 and
ei has label  in f .
Since e1 was an arbitrary ⊕ labeled edge in F we have shown the
claim. 
We use the two lemmas to count the number of ⊕ labels in different
ways: 
E= #{+ labels in f } ≤ 2F + p3 .
f

With E = n(n − 2) and 2F = (n − 1)(n − 2) this implies

p3 ≥ n − 2.

3 Nonsimple Euclidean Arrangements

We now come to the lower bound for the number of triangles in the
nonsimple case.

Proposition 2. A Euclidean nonsimple and nontrivial arrangement of

n ≥ 6 pseudolines has at least 2n/3 triangles with equality for all n = 0
(mod 3).

Proof. We distinguish two cases. First suppose that every line l of the
arrangement contains crossings of the arrangement in both open half-
spaces it defines. Consider l as a state of a sweepline going across the
arrangement. From the theory of sweeps for arrangements of pseudolines
(see e.g. [13]) we know that the sweep can make progress both in the
forward as well as in the backward direction. A progress-move pulls line
l across a crossing c of some lines of the arrangement with the property
that the portion of all lines contributing to c between c and l are free
of further crossings, i.e. are edges of the cell complex induced by the
arrangement. Hence such a move pulls l across some triangles with corner
c and an edge on l. This shows that l contributes to at least one triangle
 Triangles in Euclidean Arrangements 145

on either side. Since we assumed that every line has crossings on either
side this accounts for 2n triangles each counted at most three times and
the claim is proved in this case.
Now assume that there is a line l so that all crossings of the arrange-
ment not on l are on one side of l. If taking away l all lines cross in just
one point c then there are n − 2 triangles in the arrangement and since
we assume n ≥ 6 we are done. Else removing l from the arrangement
we still have a nontrivial arrangement which by induction has at least
2(n − 1)/3 triangles. Since l can make a sweep move to one of its sides
there is at least one triangle with an edge on l that disappeared after
removal of l (it turned into an unbounded region). His makes a total of
2(n − 1)/3 + 1 > 2n/3 triangles in the initial arrangement.
It remains to describe a family Wn of arrangements with 3n lines but
only 2n triangles. A drawing of W4 is given in Figure 5.
Let P be a regular 2n-gon with edges e1 , e2 , . . . , e2n in counterclock-
wise ordering and barycenter c. Let lines l1 , . . . , l2n be straight lines such
that li contains edge ei of P . Orient the lines such that P is to their left.
Note that li is crossed by lines li+n+1 , li+n+2 , . . . , li−1 , li+1 , li+2 , . . . li+n−1
in this order with indices being taken cyclically. The arrangement A
formed by these 2n lines has 2n triangles all adjacent to P . All the other
faces of the arrangement are quadrangles.
For every pair li , li+n of parallel lines we construct an additional line
gi . We lead g1 from the unbounded region between the positive end of l1
and the negative end of ln to the unbounded region between the positive
end of ln+1 and the negative end of l2n . The first line crossed by g1 is
l1 . Parallel to ln+1 line g1 crosses l2 , l3 , . . . , ln−1 and splits quadrangles
into two. Before entering P line g1 splits the triangle sitting over edge en
into a quadrangle and a triangle. From edge en line g1 joins to point c
and then to the opposite edge e2n to cross lines l2n , l2n−1 , . . . , ln+1 in this
order.
Define lines g2 , . . . , gn by rotational symmetry and note that g1 , . . . , gn
all cross in c. The arrangement A ∪ {g1 , g2 , . . . , gn } has the same number
of triangles as A.
So far we still have n pairs of parallel lines. Note however that without
increasing the number of triangles we may arbitrarily choose to have the
crossing of pair {li , li+n } to be on the side of the positive end of either li
or li+n . Thus Wn is itself not just one but an exponentially large class of
examples.
146 S. Felsner and K. Kriegel

Figure 5. The arrangement W4 with 12 lines and 8 triangles.

4 Triangles in Arrangements with Multiple Intersections

In his monograph Grünbaum extends the notion of arrangements in sev-

eral directions. Let an arrangement of pseudocircles be a family of closed
curves with the property that any two curves cross twice
. A digon in such
an arrangement is a face bounded by only two of the curves. Grünbaum
asks for the relationship between the number of triangles and digons in
such arrangements. In particular he conjectures [4, Conjecture 3.7] that
every digon-free arrangement of pseudocircles contains 2n − 4 triangles.
The only progress on this conjecture is a result of Snoeyink and Hersh-
berger [13]. They prove p3 ≥ 4n/3. The proof is only given for the simple
case, i.e., no three curves cross in a single point. However, it is not hard
to see that it also applies to the general case.
Based on the arrangements Wn from Section 3 it is possible to con-
struct examples of nonsimple arrangements of pseudocircles in IP with
only 4n/3 triangles. The idea is to glue two copies of Wn together such
that all faces generated by gluing are quadrangles, see Figure 6. Hence,
the result of Snoeyink and Hershberger is best possible. However, if the
arrangement is simple, i.e., no three curves meet in a single point we
think that Grünbaum’s conjecture should prove correct. For emphasis we
restate the conjecture.


Grünbaum calls this an arrangement of curves
 Triangles in Euclidean Arrangements 147

Figure 6. A digon-free arrangement of 9 two-intersecting curves and 12

triangles.

Conjecture 1. Every simple digon-free arrangement of pseudocircles con-

tains at least 2n − 4 triangles.

We feel that the spirit of Euclidean arrangements is captured well with

the following generalization. Call an arrangement of x-monotone curves
with the property that any two curves cross exactly k times a k-curve
arrangement. Again based on the family Wn it is possible to obtain k-
curve arrangements of n curves with only 2kn/3 triangles. On the other
hand we conjecture.
Conjecture 2. Every simple digon-free k-curve arrangement contains at
least k(n − 2) triangles.
If true this would obviously be best possible since gluing together k
appropriate arrangements of pseudolines with n − 2 triangles each gives
arrangements with only k(n − 2) triangles.

References
1. A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler,
Oriented Matroids, Cambridge University Press, Cambridge, 1993.
2. Z. Füredi and I. Palasti, Arrangements of lines with large number of triangles.,
Proc. Am. Math. Soc., 92 (1984), pp. 561–566.
3. J. E. Goodman, Proof of a conjecture of Burr, Grünbaum and Sloane, Discrete
Math., 32 (1980), pp. 27–35.
4. B. Grünbaum, Arrangements and spreads, Regional Conf. Ser. Math., Amer.
Math. Soc., Providence, RI, 1972.
5. H. Harborth, Some simple arrangements of pseudolines with a maximum number
of triangles., in Discrete geometry and convexity, Proc. Conf., New York 1982,
vol. 440, Ann. N. Y. Acad. Sci., 1985, pp. 31–33.
148 S. Felsner and K. Kriegel

6. D. E. Knuth, Axioms and Hulls, vol. 606 of Lecture Notes in Computer Science,
Springer-Verlag, Heidelberg, Germany, 1992.
7. F. Levi, Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade, in
Berichte über die Verhandlungen der sächsischen Akademie der Wissenschaften,
Leipzig, Mathematisch-physikalische Klasse 78, 1926, pp. 256–267.
8. G. Ringel, Teilungen der Ebenen durch Geraden oder topologische Geraden.,
Math. Z., 64 (1956), pp. 79–102.
9. J.-P. Roudneff, On the number of triangles in simple arrangements of pseudolines
in the real projective plane., Discrete Math., 60 (1986), pp. 243–251.
10. , Arrangements of lines with a minimum number of triangles are simple.,
Discrete Comput. Geom., 3 (1988), pp. 97–102.
11. , The maximum number of triangles in arrangements of pseudolines., J.
Comb. Theory, Ser. B, 66 (1996), pp. 44–74.
12. R. W. Shannon, Simplicial cells in arrangements of hyperplanes., Geom. Dedicata,
8 (1979), pp. 179–187.
13. J. Snoeyink and J. Hershberger, Sweeping arrangements of curves, in Proceed-
ings of the 5th Annual Symposium on Computational Geometry (SCG ’89), ACM
Press, 1989, pp. 354–363.