<<

. 3
( 20 .)



>>

or V ’ .

C
’∞ ∞
¡
t ¡
t
¡
t
t q¡
b
¡t
t
¡
t
¡
t
¡
B D
t
¡
A t
¡
t
¡
tc
q¡ tq
’∞ ∞
a t
¡
G F tE
¡
t
¡ t
¡
’∞ ∞


Figure 1.2: Three lines in general position (i.e. no two lines are parallel and
three lines do not intersect in one point) divide the plane into seven open faces
A, . . . , G (chambers), nine 1-dimensional faces (edges) (’∞, a), (a, b), . . . , (c, ∞),
and three 0-dimensional faces (vertices) a, b, c. Notice that 1-dimensional faces
are open intervals.
A. & A. Borovik • Mirrors and Re¬‚ections • Version 01 • 25.02.00 9

Let Σ be a ¬nite set of hyperplanes in ARn . If a and b are points in
ARn , we shall say that a and b are similarly positioned with respect to Σ
and write a ∼ b if a and b are similarly positioned with respect to every
hyperplane H ∈ Σ. Obviously ∼ is an equivalence relation. Its equivalence
classes are called faces of the hyperplane arrangement Σ (Figure 1.2). Since
Σ is ¬nite, it has only ¬nitely many faces. We emphasise that faces are
disjoint; distinct faces have no points in common.
It easily follows from the de¬nition that if F is a face and a hyperplane
H ∈ Σ contains a point in F then H contains F . The intersection L of
all hyperplanes in Σ which contain F is an a¬ne subspace, it is called the
support of F . The dimension of F is the dimension of its support L.
Topological properties of faces are described by the following result.

Proposition 1.2.1 In this notation,

• F is an open convex subset of the a¬ne space L.

• The boundary of F is the union of some set of faces of strictly smaller
dimension.

• If F and F are faces with equal closures, F = F , then F = F .

Chambers. By de¬nition, chambers are faces of Σ which are not con-
tained in any hyperplane of Σ. Also chambers can be de¬ned, in an equiv-
alent way, as connected components of

ARn H.
H∈Σ

Chambers are open convex subsets of ARn . A panel or facet of a chamber
C is a face of dimension n ’ 1 on the boundary of C. It follows from the
de¬nition that a panel P belongs to a unique hyperplane H ∈ Σ, called a
wall of the chamber C.

Proposition 1.2.2 Let C and C be two chambers. The following condi-
tions are equivalent:

• C and C are separated by just one hyperplane in Σ.

• C and C have a panel in common.

• C and C have a unique panel in common.

Lemma 1.2.3 Let C and C be distinct chambers and P their common
panel. Then
10

(a) the wall H which contains P is the only wall with a notrivial inter-
section with the set C ∪ P ∪ C , and

(b) C ∪ P ∪ C is a convex open set.


Proof. The set C ∪ P ∪ C is a connected component of what is left
after deleting from V all hyperplanes from Σ but H. Therefore H is the
only wall in σ which intersects C ∪ P ∪ C . Moreover, C ∪ P ∪ C is the
intersection of open half-spaces and hence is convex.

1.2.2 Galleries
We say that chambers C and C are adjacent if they have a panel in
common. Notice that a chamber is adjacent to itself. A gallery “ is a
sequence C0 , C1 , . . . , Cl of chambers such that Ci and Ci’1 are adjacent,
for all i = 1, . . . , l. The number l is called the length of the gallery. We say
that C0 and Cl are connected by the gallery “ and that C0 and Cl are the
endpoints of “. A gallery is geodesic if it has the minimal length among
all galleries connecting its endpoints. The distance d(C, D) between the
chambers C and D is the length of a geodesic gallery connecting them.

Proposition 1.2.4 Any two chambers of Σ can be connected by a gallery.
The distance d(D, C) between the chambers C and D equals to the number
of hyperplanes in Σ which separate C from D.

Proof. Assume that C and D are separated by m hyperplanes in Σ.
Select two points c ∈ C and d ∈ D so that the segment [c, d] does not
intersect any (n ’ 2)-dimensional face of Σ. Then the chambers which are
intersected by the segment [c, d, ] form a gallery connecting C and D, and
it is easy to see that its length is m. To prove that m = d(C, D), consider
an arbitrary gallery C0 , . . . , Cl connecting C = C0 and D = Cl . We may
assume without loss of generality that consequent chambers Ci’1 and Ci
are distinct for all i = 1, . . . , l. For each i = 0, 1, . . . , l, chose a point
ci ∈ Ci . The union

[c0 , c1 ] ∪ [c1 , c2 ] ∪ · · · ∪ [cl’1 , cl ]

is connected, and by the connectedness argument each wall H which sepa-
rates C and D has to intersect one of the segments [ci’1 , ci ]. Let P be the
common panel of Ci’1 and Ci . By virtue of Lemma 1.2.3(a), [ci’1 , ci ] ‚
Ci’1 ∪ P ∪ Ci and H has a nontrivial intersection with Ci’1 ∪ P ∪ Ci . But
then, in view of Lemma 1.2.3(b), H contains the panel P . Therefore each
A. & A. Borovik • Mirrors and Re¬‚ections • Version 01 • 25.02.00 11

of m walls separating C from D contains the common panel of a di¬erent
pair (Ci’1 , Ci ) of adjacent chambers. It is obvious now that l m.
As a byproduct of this proof, we have another useful result.
Lemma 1.2.5 Assume that the endpoints ot the gallery C0 , C1 , . . . , Cl lie
on the opposite sides of the wall H. Then, for some i = 1, . . . , l, the wall
H contains the common panel of consequtive chambers Ci’1 and Ci .
We shall say in this situation that the wall H interesects the gallery
C0 , . . . , Cl .
Another corollary of Proposition 1.2.4 is the following characterisation
of geodesic galleries.
Proposition 1.2.6 A geodesic gallery intersects each wall at most once.
The following elementary property of distance d( , ) will be very useful
in the sequel.
Proposition 1.2.7 Let D and E be two distinct adjacent chambers and H
wall separating them. Let C be a chamber, and assume that the chambers
C and D lie on the same side of H. Then
d(C, E) = d(C, D) + 1.



Proof is left to the reader as an exercise.

Exercises
1.2.1 Prove that distance d( , ) on the set of chambers of a hyperplane arrange-
ment satis¬es the triangle inequality:
d(C, D) + d(C, E) d(C, E).
1.2.2 Prove that, in the plane AR2 , n lines in general position (i.e. no lines are
parallel and no three intersect in one point) divide the plane in
1
1 + (1 + 2 + · · · + n) = (n2 + n + 2)
2
chambers. How many of these chambers are unbounded? Also, ¬nd the numbers
of 1- and 0-dimensional faces.
Hint: Use induction on n.
1.2.3 Given a line arrangement in the plane, prove that the chambers can be
coloured black and white so that adjacent chambers have di¬erent colours.
Hint: Use induction on the number of lines.
1.2.4 Prove Proposition 1.2.7.
Hint: Use Proposition 1.2.4 and Lemma 1.2.3.
12

1.3 Polyhedra

gg
¨
¨¨ g 
¨   g
¨
¡ ¢
¢
¡ ¨¨  g 
    g
 
¢
¨¨ e
¡    g
  
e ¢  
¡
d     
       g
e rrrrrrrrrrrrrrrrrrrrrrrr¢  
¡d       
       g
£ e    
¡ d
           g
    
£ e  
d £ e            g
     
d
d   g
(a) (b) (c)


Figure 1.3: Polyhedra can be unbounded (a) or without interior points (b). In
some books the term ˜polytope™ is reserved for bounded polyhedra with interior
points (c); we prefer to use it for all bounded polyhedra, so that (b) is a polytope
in our sense.

A polyhedral set, or polyhedron in ARn is the intersection of the ¬nite
number of closed half spaces. Since half spaces are convex, every polyhe-
dron is convex. Bounded polyhedra are called polytopes (Figure 1.3).



q q

=
q q



Figure 1.4: A polyhedron is the union of its faces.

Let ∆ be a polyhedron represented as the intersection of closed halfs-
paces X1 , . . . , Xm bounded by the hyperplanes H1 , . . . , Hm . Consider the
hyperplane con¬guration Σ = { H1 , . . . , Hm }. If F is a face of Σ and has a
point in common with ∆ then F belongs to ∆. Thus ∆ is a union of faces.
Actually it can be shown that ∆ is the closure of exactly one face of Σ.
0-dimensional faces of ∆ are called vertices, 1-dimensional edges.
The following result is probably the most important theorem about
polytopes.
Theorem 1.3.1 A polytope is the convex hull of its vertices. Vice versa,
given a ¬nite set E of points in ARn , their convex hull is a polytope whose
vertices belong to E.
A. & A. Borovik • Mirrors and Re¬‚ections • Version 01 • 25.02.00 13

As R. T. Rockafellar characterised it [Roc, p. 171],
This classical result is an outstanding example of a fact which is a
completely obvious to geometric intuition, but which wields impor-
tant algebraic content and not trivial to prove.

We hope this quotation is a su¬cient justi¬cation for our decision not
include the proof of the theorem in our book.

Exercises
1.3.1 Let ∆ be a tetrahedron in AR3 and Σ the arrangement formed by the
planes containing facets of ∆. Make a sketch analogous to Figure 1.2. Find
the number of chambers of Σ. Can you see a natural correspondence between
chambers of Σ and faces of ∆?
Hint: When answering the second question, consider ¬rst the 2-dimensional
case, Figure 1.2.




x3
T
(0, 0, 1)
h The regular 2-simplex is the set of solu-

h   tions of the system of simultaneous in-

<<

. 3
( 20 .)



>>