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-