Agoston M.K. Computer Graphics and Geometric Modelling: Mathematics

Подождите немного. Документ загружается.

1.4.4. Use the Gram-Schmidt algorithm to replace the vectors (1,0,1), (0,1,1), and (2,-3,-1) by

an orthonormal set of vectors that spans the same subspace.

1.4.5. This exercise shows that equation (1.14) in Theorem 1.4.6 gives the wrong answer if the

vectors u

do not form an orthonormal basis. Consider the vector v = (1,2,3) in R

. Its

orthogonal projection onto R

should clearly be (1,2,0). Let u

and u

be a basis for R

and let

(a) If u

= (1,0,0) and u

= , show that w π (1,2,0).

(b) If u

= (2,0,0) and u

= (0,3,0), show that w π (1,2,0).

Section 1.5

1.5.1. Suppose that X is a k-dimensional plane in R

and that

where p, q Œ R

and V and W are k-dimensional vector subspaces of R

. Show that V = W.

1.5.2. Fill in the missing details in the proof of Proposition 1.5.2.

1.5.3. Prove that the intersection of two planes is a plane.

1.5.4. Prove that if X is a plane, then aff(X) = X.

1.5.5. Prove Lemma 1.5.6.

1.5.6. Prove Lemma 1.5.7.

1.5.7. (a) Prove that two lines in R

are parallel if and only if they have parallel direction

vectors.

(b) Let L and L¢ be lines in R

deﬁned by the equations ax + by = c and a¢x + b¢y = c¢,

respectively. Prove that L and L¢ are parallel if and only if a¢=ka and b¢=kb for

some nonzero constant k.

1.5.8. Prove Theorem 1.5.10.

1.5.9. Find a basis for the plane x - 3y + 2z = 12 in R

1.5.10. Find the equation of all planes in R

that are orthogonal to the vector (1,2,3).

1.5.11. Find the equation of the plane containing the points (1,0,1), (3,-1,1), and (0,1,1).

1.5.12. Find the equation for the plane in R

that contains the point (1,2,1) and is parallel to

the plane deﬁned by x - y - z = 7.

1.5.13. Find an equation for all planes in R

that contain the point (1,2,1) and are orthogonal

to the plane deﬁned by x - y - z = 7.

1.5.14. Find an orthonormal basis for the plane x + 2y - z = 3.

1.5.15. Let X be the plane deﬁned by 2x + y - 3z = 7. Let v = (2,1,0).

(a) Find the orthogonal projection of v on X.

(b) Find the orthogonal complement of v with respect to X.

XpvvV qwwW=+ Œ

{}

=+ Œ

{}

0,,

wvuu vuu=∑

()

+∑

()

11 22

1.12 Exercises 59

1.5.16. Find the point-normals equation for the line

1.5.17. Determine whether the halfplanes 2y - x ≥ 0, y - 2x + 2 ≥ 0, and -4y + 2x + 4 £ 0 have

a nonempty intersection or not.

1.5.18. Let V and W be subspaces of R

of dimension s and t, respectively. Assume that s + t

≥ n. Prove that V is transverse to W if and only if one of the following holds:

(a) V + W = R

(b) If v

, v

,..., v

and w

, w

,..., w

are bases for V and W, respectively, then the

vectors v

, v

,..., v

, w

,..., w

span R

1.5.19. Deﬁnition. Any subset X in C

of the form

where p is a ﬁxed point and the v

, v

,..., v

are ﬁxed linearly independent vectors in

is called a complex k-dimensional plane (through p). If k = 1, then X is called a

complex line.

(a) Prove that a complex line in C

can also be expressed as the set of points (x,y) Œ

satisfying an equation of the form

for ﬁxed a, b, c Œ C with (a,b) π (0,0).

(b) Prove that the real points of a complex plane in C

lie on a plane in R

Section 1.6

1.6.1. Prove Lemma 1.6.1.

1.6.2. Determine whether the following pairs of ordered bases of R

determine the same

orientation:

(a) ((1,-2), (-3,2)) and ((1,0), (-2,3))

(b) ((-1,1), (1,2)) and ((1,-2), (1,-4))

Solve this exercise in two ways: First, use only the deﬁnition of orientation and then

check your answer using the matrix approach of Lemma 1.6.4.

1.6.3. Why is “Does ((1,-2), (-2,4)) induce the standard orientation of the plane?” a mean-

ingless question?

1.6.4. (a) Find a vector (a,b) so that the basis ((-2,-3), (a,b)) determines the standard orien-

tation of the plane.

(b) Find a vector (a,b,c) so that the basis ((2,-1,0), (-2,-1,0), (a,b,c)) determines the

standard orientation of 3-space.

ax by c+=,

Xp v v v C=+ + ++ Œ

{}

tt ttt t

kk k11 2 2 1 2

... , ,..., ,

60 1 Linear Algebra Topics

1.6.5. Show that the angle between oriented hyperplanes (X,s) and (Y,t) is well deﬁned.

Speciﬁcally, show that it does not depend on the choice of the normal vectors v

and

for X and Y, in the deﬁnition.

1.6.6. Let L be an oriented line and let p and q be two points on L. Prove that

1.6.7. Let (V,s) and (W,t) be two oriented n-dimensional vector spaces and let T:V Æ W be

a nonsingular linear transformation. Show that T is orientation preserving if

for any one ordered bases (v

,...,v

) of V with the property that s=[v

,...,v

Section 1.7

1.7.1. Show that each halfplane in R

is convex.

1.7.2. Show that if X

, X

,..., X

are convex sets, then their intersection is convex.

1.7.3. If X is convex, show that conv(X) = X.

1.7.4. Show that conv({p

}) = [p

1.7.5. Let s be the two-dimensional simplex deﬁned by the vertices v

= (-2,-1), v

= (3,0), and

= (0,2). The points of s can be described either with Cartesian or barycentric

coordinates (with respect to the vertices listed in the order given above).

(a) Find the Cartesian coordinates of the point p whose barycentric coordinates are

(b) Find the barycentric coordinates of the point q whose Cartesian coordinates are

(0,0).

1.7.6. Show that the simplicial map from the 1-simplex [2,5] to the 1-simplex [3,7] that sends

2 to 3 and 5 to 7 agrees with the “standard” linear map between the intervals, namely,

1.7.7. Generalize Exercise 1.7.6 and show that the simplicial map from [a,b] to [c,d] agrees

with the standard linear map.

Section 1.8

1.8.1. Let

Find a matrix P so that P

-1

AP is a diagonal matrix.

A =

gx x

()

,,.

()() ( )

[]

TT T

vv v

, ,...,

pq p q

pq pq L

pq pq

0, ,

if the vector induces the same orientation on and

if induces the opposite orientation on L

1.12 Exercises 61

Section 1.9

1.9.1. Let

Find a nonsingular matrix C so that CAC

is a diagonal matrix.

Section 1.10

1.10.1. Prove Proposition 1.10.3. (Hint: First show that, if e

, e

, and e

are the standard basis

vectors in R

, then e

¥ e

= e

, e

¥ e

=-e

, and e

¥ e

= e

1.10.2. Prove Proposition 1.10.4.

Note: The properties will not be hard to prove if one uses the deﬁnition and basic

properties of determinants. This shows once again how valuable a good deﬁnition is

because some textbooks, especially in the physical sciences, deal with cross products

in very messy ways. Although it is our intuition which leads us to useful concepts, it

is usually a good idea not to stop with the initial insight but probe a little further and

really capture their essence.

1.10.3. Prove that if u, v Œ R

are orthogonal unit vectors, then (u ¥ v) ¥ u = u.

1.10.4. Let u, v, w Œ R

. Prove

(a) u •(v ¥ w) =

(b) u •(v ¥ w) = v•(w ¥ u) = w •(u ¥ v).

(The quantity u •(v ¥ w) is called the triple product of u, v, and w.)

det

A =

12 3

25 4

348

62 1 Linear Algebra Topics

CHAPTER 2

Afﬁne Geometry

2.1 Overview

The next two chapters deal with the analytic and geometric properties of some impor-

tant transformations of R

. This chapter discusses the group of afﬁne maps and its

two important subgroups, the group of similarities and the group of motions. Afﬁne

maps are the transformations that preserve parallelism. Similarities are the afﬁne

transformations that preserve angles. Motions are the distance-preserving similarities

and their study is equivalent to the study of metric properties of Euclidean space. As

a historical note, this reduction of geometric problems to algebra (namely the study

of certain groups in our case) was initiated by the German mathematician Felix Klein

at the end of the 19

century.

Except for some deﬁnitions and a few basic facts, the ﬁrst part of the chapter (Sec-

tions 2.2–2.4) concentrates on the important special case of the plane R

. Presenting

a lot of details in the planar case where it is easier to draw pictures should make it

easier to understand what happens in higher dimensions since the generalizations are,

by and large, straightforward.

Motions are probably the most well-known afﬁne maps and we analyze planar

motions in quite some detail in Section 2.2. Section 2.2.8 introduces the concept of a

frame. Frames are an extremely useful way to deal with motions and changing from

one coordinate system to another. It is not an overstatement to say that a person who

understands frames will ﬁnd working with motions a triviality. There is a brief dis-

cussion of similarities in Section 2.3 and afﬁne maps in Section 2.4. Parallel projec-

tions are deﬁned in Section 2.4.1. Section 2.5 extends the main ideas from the plane

to higher dimensions. The important case of motions in R

is treated separately in

Sections 2.5.1 and 2.5.2.

There is not enough space to prove everything in this chapter and it will be up to

the reader to ﬁll in missing details or to look them up in the references. Hopefully,

the details we do provide in conjunction with what we did in Chapter 1 will make

ﬁlling in missing details easy in most cases. Unproved facts are included because it

was felt that they were worth knowing about and help as motivation for the next

chapter on projective transformations. References to where proofs may be found are

given in those cases where difﬁcult results are stated but not proved.

Finally, we want to emphasize one point. The single most important topic in

this chapter is that of frames. Frames are so simple (they are just orthonormal bases),

yet if the reader masters their use, then dealing with transformations will be a

snap!

2.2 Motions

Deﬁnition. A transformation M:R

Æ R

is called a motion or isometry or congru-

ent transformation of R

for every pair of points p, q Œ R

In simple terms, motions are distance-preserving maps. If one concentrates on

that aspect, then the term “isometry” is the one that mathematicians normally use

when talking about distance-preserving maps between arbitrary spaces. The term

“motion” is popular in the context of R

2.2.1. Theorem.

(1) Motions preserve the betweenness relation.

(2) Motions preserve collinearity and noncollinearity.

(3) Motions send lines to lines.

Proof. To prove (1), let M be a motion and let C be a point between two points

A and B. Let (A¢,C¢,B¢) = M(A,C,B). We must show that C¢ is between A¢ and B¢.

Now

The ﬁrst and third equality above follows from the deﬁnition of a motion. The second

follows from Proposition 1.2.3. Using Proposition 1.2.3 again proves (1). Parts (2) and

(3) of the theorem clearly follow from (1).

2.2.2. Lemma. Let M be a motion. If

then

M M tM M t M tMCA AB A B

()

() ()

()()

()

CA AB A B=+ =-

()

+ttt1,

¢¢

¢¢+ ¢¢

AB =AB

=AC CB

=AC CB.

MMpqpq

() ()

= ,

64 2 Afﬁne Geometry

Proof. Let (A¢,B¢,C¢) = M(A,B,C). Since M is a motion,

The proof is divided into cases.

Case 1. 0 £ t £ 1.

Case 2. 1 < t.

Case 3. t < 0.

In Case 1, C is between A and B. By Proposition 1.2.4, only

are solutions to the equation

Of these, only X

lies between A¢ and B¢. By part (1) of Theorem 2.2.1 we have that

C¢ = X

, which proves the lemma. The proofs in the other two cases are similar and

are left as exercises to the reader. Note that in Case 2 B is between A and C and in

Case 3 A is between C and B.

2.2.3. Lemma. Let L

and L

be two distinct lines in the plane which intersect in a

point C. Let P be any point not on either of these lines. Then there exist two distinct

points A and B on L

and L

, respectively, so that P lies on the line L determined by

A and B.

Proof. See Figure 2.1. Let v

and v

be direction vectors for L

and L

, respectively.

These vectors are linearly independent since the lines are not parallel. Let A = C + av

be any point on L

with a > 0 and let L be the line determined by P and A. To ﬁnd

the intersection of L and L

, we must solve the equation

PPACv+=+st

¢¢= ¢¢AX ABt.

X A AB X A AB

=¢+ ¢¢ =¢- ¢¢tor t

¢¢= = = ¢¢A C AC AB A Btt.

2.2 Motions 65

Figure 2.1. Proving Lemma 2.2.3.

for real numbers s and t. This equation can be rewritten as

(2.1)

Since v

and v

are linearly independent, s cannot be 1 and equation (2.1) has a unique

solution for s and t. Let B = P + sPA.

2.2.4. Lemma. A motion M is a one-to-one and onto map.

Proof. The ﬁrst part, that M is one-to-one, is easy, because if the distance between

the images of two points under M is zero, then so is the distance between the two

points by the deﬁnition of a motion.

Showing that M is onto is harder and we only prove it in the planar case here.

See [Gans69] for the general case. We begin by proving a stronger version of Theorem

2.2.1 (3).

Claim. M maps lines onto lines.

Let L be a line. We already know that M(L) is contained in a line L¢. Let C¢ be any

point of L¢. We must show that there is a point C in L with M(C) = C¢. To this end,

choose any two distinct points A and B of L and let (A¢,B¢) = M(A,B). Then C¢ = A¢ +

tA¢B¢ for some t. It follows from Lemma 2.2.2 that C¢ = M(A + tAB) and the claim is

proved.

We are ready to prove that planar motions are onto. See Figure 2.2. Let P¢ be any

point of R

. We must show that P¢ = M(P) for some point P. Take three noncollinear

points A, B, and C and let (A¢,B¢,C¢) = M(A,B,C). Let L

¢ be the line that contains the

points A¢ and B¢ and let L

¢ be the line that contains A¢ and C¢. We just showed that

all the points on these two lines are in the image of M. Assume that P¢ is not on these

two lines. By Lemma 2.2.3 there are two points D¢ and E¢ on these lines so that P¢ is

on the line L¢ determined by D¢ and E¢ and hence in the image of M. The planar case

of Lemma 2.2.4 is proved.

Although much of what we shall prove about motions depends only on their dis-

tance-preserving property and not on their domain, the domain can be important.

The following example shows that Lemma 2.2.4 deﬁnitely uses the fact that the

domain of the motion is all of the plane:

sa t svv PC

1-=-

()

66 2 Afﬁne Geometry

C¢

B¢

P¢

D¢

E¢

L¢

A¢

Figure 2.2. Proving motions are onto maps.

2.2.5. Example. Let X = { (x,y) | x > 0 } Õ R

and deﬁne the distance-preserving map

T:X ÆX by T(x,y) = (x + 1,y). The map T is clearly not onto.

2.2.6. Theorem. Motions form a group under composition.

Proof. Exercise.

The idea of a motion as a distance-preserving map is intuitively simple to under-

stand, but it is not very useful for making computations. In the process of deriving a

simple analytical description of motions, we shall not only get a lot of geometric

insights but also get practice in using linear algebra to solve geometric problems. We

begin our study of motions with an approach that is used time and again in mathe-

matics. Namely, if faced with the problem of classifying a set of objects, ﬁrst isolate

as many simple and easy-to-understand elements as possible and then try to show

that these elements can be used as building blocks from which all elements of the

class can be “generated.”

2.2.1 Translations

The simplest types of motions are translations.

Deﬁnition. Any map T :R

ÆR

of the form

(2.2)

where v is a ﬁxed vector, is called a translation of R

. The vector v is called the trans-

lation vector of T.

Writing things out in terms of coordinates, it is easy to see that a map T(x

...,x

) = (x

¢,x

¢,...,x

¢) is a translation if and only if it is deﬁned by equations of

the form

(2.3)

···

where the c

are ﬁxed real numbers. Clearly, (c

,...,c

) is the translation vector of

T in this case.

2.2.1.1. Theorem. Translations are motions.

Proof. This is a simple exercise for the reader.

Here are several simple interesting properties of translations.

2.2.1.2. Proposition. A translation T with nonzero translation vector v satisﬁes the

following properties:

xxc

nnn

=+,

xxc

222

xxc

111

T p=p v

()

+ ,

2.2 Motions 67

(1) T has no ﬁxed points.

(2) T takes lines to lines with the same direction vector (or slope, in the case of

the plane).

(3) The only lines ﬁxed by T are those with direction vector v. In the case of the

plane, the only lines ﬁxed by T are those whose slope is the same as the slope

of one of their direction vectors.

Proof. (1) and (2) are left as exercises for the reader. To prove (3), consider a line L

through a point p

with direction vector w. If T ﬁxes L, then T maps a point p

+ tw

on L to another point on L that will have the form p

+ sw. Therefore,

and so w is a multiple of v. The converse is just as easy.

In case of the plane, assume that the line L ﬁxed by T is deﬁned by the equation

(2.4)

The line L has slope -a/b (the case of a vertical line where b is zero is left as an exer-

cise for the reader). If v = (h,k), then the slope of v is k/h. Choose a point (x,y) on L.

Since T(x,y) = (x + h,y + k) is assumed to lie on L, that point must also satisfy equa-

tion (2.4), that is,

Using the identity (2.4) in this last equation implies that ah + bk = 0. This shows that

k/h =-a/b and we are done.

2.2.2 Rotations in the Plane

Another intuitively simple motion is a rotation of the plane.

Deﬁnition. Let qŒR. A map R:R

ÆR

of the form R(r,a) = (r,a+q), where points

have been expressed in polar coordinates, is called a rotation about the origin through

an angle q.

See Figure 2.3. Using polar coordinates was an easy way to deﬁne rotations about

the origin, but is not convenient from a computational point of view. To derive the

equations for a rotation R in Cartesian coordinates, we use the basic correspondence

between the polar coordinates (r,a) and Cartesian coordinates (x,y) for a point p:

(2.5)

Let R(x,y) = (x¢,y¢). Since R(r,a) = (r,a+q),

cos

sin

ax h by k c+

()

= .

ax by c+=.

pw pw

pwv

+= +

()

=++

sT t

68 2 Afﬁne Geometry