<< Предыдущая стр. 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 стр.)ОГЛАВЛЕНИЕ Следующая >>