CMSC 425 Lecture Notes - Lecture 5: Geometric Programming, Linear Algebra, Object-Oriented Programming
15 May 2018
School
Department
Course
Professor
CMSC 425 Dave Mount & Roger Eastman
CMSC 425: Lecture 5
More on Geometry and Geometric Programming
More Geometric Programming: In this lecture we continue the discussion of basic geometric
programming from the previous lecture. We will discuss coordinate systems for affine and
Euclidean geometry, cross-product and orientation testing, and affine transformations.
Local and Global Frames of Reference: Last time we introduced the basic elements of affine
and Euclidean geometry: points and (free) vectors. However, as of yet we have no mechanism
for representing these objects. Recall that points are to be thought of as locations in space
and (free) vectors represent direction and magnitude, but are not tied down to a particular
location in space. We seek a “frame of reference” from which to describe vectors and points.
This is called a coordinate frame.
There is a global coordinate frame (also called the world frame) from which all geometric
objects are described. It is convenient in geometric programming to define various local
frames as well. For example, suppose we have a vehicle driving around a city. We might
attach a local frame to this vehicle in order to describe the relative positions of objects and
characters within the vehicle. The position of the vehicle itself is then described relative to
the global frame. This raises the question of how to convert between the local coordinates
used to define objects within the vehicle to their global coordinates.
Bases, Vectors, and Coordinates: The first question is how to represent points and vectors in
affine space. We will begin by recalling how to do this in linear algebra, and generalize from
there. We know from linear algebra that if we have 2-linearly independent vectors, ~u0and ~u1
in 2-space, then we can represent any other vector in 2-space uniquely as a linear combination
of these two vectors (see Fig. 1(a)):
~v =α0~u0+α1~u1,
for some choice of scalars α0,α1.
u0
u1
v
u0
u1
(a)
v= 2u0+ 3u1
x
y
(b)
w= 3e0+ 2e1
e0
e1
w[F]= (3,2)
v[F]= (2,3)
Fig. 1: Bases and linear combinations in linear algebra (a) and the standard basis (b).
Thus, given any such vectors, we can use them to represent any vector in terms of a pair of
scalars (α0, α1). In general dlinearly independent vectors in dimension dis called a basis.
The most convenient basis to work with consists of two vectors, each of unit length, that are
orthogonal to each other. Such a collection of vectors is said to be orthonormal. The standard
basis consisting of the x- and y-unit vectors is an example of such a basis (see Fig. 1(b)).
Lecture 5 1 Spring 2018
CMSC 425 Dave Mount & Roger Eastman
Note that we are using the term “vector” in two different senses here, one as a geometric
entity and the other as a sequence of numbers, given in the form of a row or column. The
first is the object of interest (i.e., the abstract data type, in computer science terminology),
and the latter is a representation. As is common in object oriented programming, we should
“think” in terms of the abstract object, even though in our programming we will have to get
dirty and work with the representation itself.
Coordinate Frames and Coordinates: Now let us turn from linear algebra to affine geometry.
Again, let us consider just 2-dimensional space. To define a coordinate frame for an affine
space we would like to find some way to represent any object (point or vector) as a sequence
of scalars. Thus, it seems natural to generalize the notion of a basis in linear algebra to define
a basis in affine space. Note that free vectors alone are not enough to define a point (since we
cannot define a point by any combination of vector operations). To specify position, we will
designate an arbitrary point, denoted O, to serve as the origin of our coordinate frame. Let
~u0and ~u1be a pair of linearly independent vectors. We already know that we can represent
any vector uniquely as a linear combination of these two basis vectors. We can represent any
point pby adding a vector to O(in particular, the vector p−O). It follows that we can
represent any point pin the following form:
p=α0~u0+α1~u1+O,
for some pair of scalars α0and α1. This suggests the following definition.
Definition: Acoordinate frame for a d-dimensional affine space consists of a point (which
we will denote O), called the origin of the frame, and a set of dlinearly independent
basis vectors.
Given the above definition, we now have a convenient way to express both points and vectors.
As with linear algebra, the most natural type of basis is orthonormal. Given an orthonormal
basis consisting of origin Oand unit vectors ~e0and ~e1, we can express any point pand any
vector ~v as:
p=α0·~e0+α1·~e1+Oand ~v =β0·~e0+β1·~e1
for scalars α0,α1,β0, and β1.
In order to convert this into a coordinate system, let us entertain the following “notational
convention.” Define 1·O=Oand 0·O=~
0 (the zero vector). Note that these two expressions
are blatantly illegal by the rules of affine geometry, but this convention makes it possible to
express the above equations in a common (homogeneous) form (see Fig. 2):
p=α0·~e0+α1·~e1+ 1 ·Oand ~v =β0·~e0+β1·~e1+ 0 ·O.
This suggests a nice method for expressing both points and vectors using a common notation.
For the given coordinate frame F= (~e0, ~e1,O) we can express the point pand the vector ~v as
p[F]= (α0, α1,1) and ~v[F]= (β0, β1,0)
(see Fig. 2).
Lecture 5 2 Spring 2018
Document Summary
More geometric programming: in this lecture we continue the discussion of basic geometric programming from the previous lecture. We will discuss coordinate systems for a ne and. Euclidean geometry, cross-product and orientation testing, and a ne transformations. Local and global frames of reference: last time we introduced the basic elements of a ne and euclidean geometry: points and (free) vectors. However, as of yet we have no mechanism for representing these objects. Recall that points are to be thought of as locations in space and (free) vectors represent direction and magnitude, but are not tied down to a particular location in space. We seek a frame of reference from which to describe vectors and points. There is a global coordinate frame (also called the world frame) from which all geometric objects are described. It is convenient in geometric programming to de ne various local frames as well. For example, suppose we have a vehicle driving around a city.
