nach oben

2011 | Buch

Kapitel lesen Erstes Kapitel lesen

Geometric Methods and Applications

For Computer Science and Engineering

verfasst von: Jean Gallier

Verlag: Springer New York

Buchreihe : Texts in Applied Mathematics

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book is an introduction to the fundamental concepts and tools needed for solving problems of a geometric nature using a computer. It attempts to fill the gap between standard geometry books, which are primarily theoretical, and applied books on computer graphics, computer vision, robotics, or machine learning.

This book covers the following topics: affine geometry, projective geometry, Euclidean geometry, convex sets, SVD and principal component analysis, manifolds and Lie groups, quadratic optimization, basics of differential geometry, and a glimpse of computational geometry (Voronoi diagrams and Delaunay triangulations). Some practical applications of the concepts presented in this book include computer vision, more specifically contour grouping, motion interpolation, and robot kinematics.

In this extensively updated second edition, more material on convex sets, Farkas’s lemma, quadratic optimization and the Schur complement have been added. The chapter on SVD has been greatly expanded and now includes a presentation of PCA.

The book is well illustrated and has chapter summaries and a large number of exercises throughout. It will be of interest to a wide audience including computer scientists, mathematicians, and engineers.

Reviews of first edition:

"Gallier's book will be a useful source for anyone interested in applications of geometrical methods to solve problems that arise in various branches of engineering. It may help to develop the sophisticated concepts from the more advanced parts of geometry into useful tools for applications." (Mathematical Reviews, 2001)

"...it will be useful as a reference book for postgraduates wishing to find the connection between their current problem and the underlying geometry." (The Australian Mathematical Society, 2001)

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

What is geometry? According to Veblen and Young [8], geometry deals with the properties of figures in space. Etymologically, geometry means the practical science of measurement. No wonder geometry plays a fundamental role in mathematics, physics, astronomy, and engineering. Historically, as explained in more detail by Coxeter [1], geometry was studied in Egypt about 2000 B.C. Then, it was brought to Greece by Thales (640–456 B.C.). Thales also began the process of abstracting positions and straight edges as points and lines, and studying incidence properties. This line of work was greatly developed by Pythagoras and his disciples, among which we should distinguish Hippocrates. Indeed, Hippocrates attempted a presentation of geometry in terms of logical deductions from a few definitions and assumptions. But it was Euclid (about 300 B.C.) who made fundamental contributions to geometry, recorded in his immortal Elements, one of the most widely read books in the world.

Jean Gallier

Chapter 2. Basics of Affine Geometry

Abstract

Geometrically, curves and surfaces are usually considered to be sets of points with some special properties, living in a space consisting of “points.” Typically, one is also interested in geometric properties invariant under certain transformations, for example, translations, rotations, projections, etc. One could model the space of points as a vector space, but this is not very satisfactory for a number of reasons. One reason is that the point corresponding to the zero vector (0), called the origin, plays a special role, when there is really no reason to have a privileged origin. Another reason is that certain notions, such as parallelism, are handled in an awkward manner. But the deeper reason is that vector spaces and affine spaces really have different geometries. The geometric properties of a vector space are invariant under the group of bijective linear maps, whereas the geometric properties of an affine space are invariant under the group of bijective affine maps, and these two groups are not isomorphic. Roughly speaking, there are more affine maps than linear maps.

Jean Gallier

Chapter 3. Basic Properties of Convex Sets

Abstract

Convex sets play a very important role in geometry. In this chapter we state and prove some of the “classics” of convex affine geometry: Carath’eodory’s theorem, Radon’s theorem, Helly’s theorem, and Krein and Millman’s theorem. These theorems share the property that they are easy to state, but they are deep, and their proof, although rather short, requires a lot of creativity. We introduce the notions of separating and supporting hyperplanes, of vertices, and of extreme points. We also define centerpoints and prove their existence.

Jean Gallier

Chapter 4. Embedding an Affine Space in a Vector Space

Abstract

For all practical purposes, curves and surfaces live in affine spaces. A disadvantage of the affine world is that points and vectors live in disjoint universes. It is often more convenient, at least mathematically, to deal with linear objects (vector spaces, linear combinations, linear maps), rather than affine objects (affine spaces, affine combinations, affine maps). Actually, it would also be advantageous if we could manipulate points and vectors as if they lived in a common universe, using perhaps an extra bit of information to distinguish between them if necessary.

Jean Gallier

Chapter 5. Basics of Projective Geometry

Abstract

For a novice, projective geometry usually appears to be a bit odd, and it is not obvious to motivate why its introduction is inevitable and in fact fruitful. One of the main motivations arises from algebraic geometry.

Jean Gallier

Chapter 6. Basics of Euclidean Geometry

Abstract

In affine geometry it is possible to deal with ratios of vectors and barycenters of points, but there is no way to express the notion of length of a line segment or to talk about orthogonality of vectors. A Euclidean structure allows us to deal with metric notions such as orthogonality and length (or distance).

Jean Gallier

Chapter 7. Separating and Supporting Hyperplanes

Abstract

Now that we have a solid background in Euclidean geometry, we can go deeper into our study of convex sets begun in Chapter 3. This chapter is devoted to a thorough study of separating and supporting hyperplanes. We prove two geometric versions of the Hahn–Banach theorem, from which we derive separation results for various kinds of pairs of convex sets (open, closed, compact). We prove various versions of Farkas’s lemma, a basic result in the theory of linear programming. We also discuss supporting hyperplanes and prove an important proposition due to Minkowski.

Jean Gallier

Chapter 8. The Cartan–Dieudonné Theorem

Abstract

In this chapter the structure of the orthogonal group is studied in more depth. In particular, we prove that every isometry in O(n) is the composition of at most n reflections about hyperplanes (for n ≥ 2, see Theorem 8.1). This important result is a special case of the “Cartan–Dieudonn’e theorem” (Cartan [4], Dieudonn’e [6]). We also prove that every rotation in SO(n) is the composition of at most n flips (for n ≥ 3).

Jean Gallier

Chapter 9. The Quaternions and the Spaces S 3, SU(2), SO(3), and ℝ ℙ3

Abstract

In this chapter, we discuss the representation of rotations of ℝ³ in terms of quaternions. Such a representation is not only concise and elegant, it also yields a very efficient way of handling composition of rotations. It also tends to be numerically more stable than the representation in terms of orthogonal matrices.

Jean Gallier

Chapter 10. Dirichlet–Voronoi Diagrams and Delaunay Triangulations

Abstract

In this chapter we present the concepts of a Voronoi diagram and of a Delaunay triangulation. These are important tools in computational geometry, and Delaunay triangulations are important in problems where it is necessary to fit 3D data using surface splines. It is usually useful to compute a good mesh for the projection of this set of data points onto the xy-plane, and a Delaunay triangulation is a good candidate. Our presentation will be rather sketchy.We are primarily interested in defining these concepts and stating their most important properties without proofs. For a comprehensive exposition of Voronoi diagrams, Delaunay triangulations, and more topics in computational geometry, our readers may consult O’Rourke [10], Preparata and Shamos [11], Boissonnat and Yvinec [2], de Berg, Van Kreveld, Overmars, and Schwarzkopf [1], or Risler [12]. The survey by Graham and Yao [7] contains a very gentle and lucid introduction to computational geometry.

Jean Gallier

Chapter 11. Basics of Hermitian Geometry

Abstract

In this chapter we generalize the basic results of Euclidean geometry presented in Chapter 6 to vector spaces over the complex numbers. Such a generalization is inevitable, and not simply a luxury. For example, linear maps may not have real eigenvalues, but they always have complex eigenvalues. Furthermore, some very important classes of linear maps can be diagonalized if they are extended to the complexification of a real vector space. This is the case for orthogonal matrices, and, more generally, normal matrices. Also, complex vector spaces are often the natural framework in physics or engineering, and they are more convenient for dealing with Fourier series. However, some complications arise due to complex conjugation. Recall that for any complex number z ∈ $\mathbb{C} $ , if z = x+iy where x, y ∈ ℝ, we let ℜz = x, the real part of z, and ℑz = y, the imaginary part of z. We also denote the conjugate of z = x+iy by $\bar{z}$ = x-iy, and the absolute value (or length, or modulus) of z by |z|. Recall that |z|2 = z$\bar{z}$ = x ² +y ². There are many natural situations where a map ϕ : E × E $\mathbb{C} $ is linear in its first argument and only semilinear in its second argument, which means that ϕ(u,µv) = µ(u,v), as opposed to ϕ(u, $\bar{\mu}$ v) = µϕ(u,v). For example, the natural inner product to deal with functions f : ℝ→ $\mathbb{C} $ , especially Fourier series, is $\langle{f,g}\rangle = \int\limits_{\pi}^{-\pi}f(x)\overline{g(x)}dx,$ which is semilinear (but not linear) in g.

Jean Gallier

Chapter 12. Spectral Theorems in Euclidean and Hermitian Spaces

Abstract

The goal of this chapter is to show that there are nice normal forms for symmetric matrices, skew-symmetric matrices, orthogonal matrices, and normal matrices. The spectral theorem for symmetric matrices states that symmetric matrices have real eigenvalues and that they can be diagonalized over an orthonormal basis. The spectral theorem for Hermitian matrices states that Hermitian matrices also have real eigenvalues and that they can be diagonalized over a complex orthonormal basis. Normal matrices can be block diagonalized over an orthonormal basis with blocks having size at most two, and there are refinements of this normal form for skewsymmetric and orthogonal matrices.

Jean Gallier

Chapter 13. Singular Value Decomposition (SVD) and Polar Form

Abstract

In this section we assume that we are dealing with a real Euclidean space E. Let $ f : E \rightarrow E $ be any linear map. In general, it may not be possible to diagonalize f. We show that every linear map can be diagonalized if we are willing to use two orthonormal bases. This is the celebrated singular value decomposition (SVD). A close cousin of the SVD is the polar form of a linear map, which shows how a linear map can be decomposed into its purely rotational component (perhaps with a flip) and its purely stretching part.

Jean Gallier

Chapter 14. Applications of SVD and Pseudo-inverses

Abstract

This chapter presents several applications of SVD. The first one is the pseudoinverse, which plays a crucial role in solving linear systems by the method of least squares. The second application is data compression. The third application is principal component analysis (PCA), whose purpose is to identify patterns in data and understand the variance–covariance structure of the data. The fourth application is the best affine approximation of a set of data, a problem closely related to PCA.

Jean Gallier

Chapter 15. Quadratic Optimization Problems

Abstract

In this chapter, we consider two classes of quadratic optimization problems that appear frequently in engineering and in computer science (especially in computer vision): 1. Minimizing

$$f(x)=\frac{1}{2}x^\top Az+x^\top b$$

over all $x \varepsilon \mathbb{R}^n$, or subject to linear or affine constraints. 2. Minimizing

$$f(x)=\frac{1}{2}x^\top Az+x^\top b$$

over the unit sphere.

Jean Gallier

Chapter 16. Schur Complements and Applications

Abstract

Schur complements arise naturally in the process of inverting block matrices of the form

$$M=\left (\begin{array}{cc} A&B\\ C &D\end{array} \right )\!$$

and in characterizing when symmetric versions of these matrices are positive definite or positive semidefinite. These characterizations come up in various quadratic optimization problems; see Boyd and Vandenberghe [1], especially Appendix B. In the most general case, pseudo-inverses are also needed.

Jean Gallier

Chapter 17. Quadratic Optimization and Contour Grouping

Abstract

This chapter presents a new and exciting application of quadratic optimization methods to the problem of contour grouping in computer vision. It turns out that this problem leads to finding the local maxima of a Hermitian matrix depending on a parameter. We are thus led to the problem of finding the derivative of an eigenvalue and the derivative of some eigenvector associated with this eigenvalue, in the case of a normal matrix. The problem also leads naturally to the consideration of the field of values of a matrix, a concept studied as early as 1918 by Toeplitz and Hausdorff. We prove that the field of values is convex, a theorem due to Toeplitz and Hausdorff. This fact is helpful in improving the search for local maxima.

Jean Gallier

Chapter 18. Basics of Manifolds and Classical Lie Groups: The Exponential Map, Lie Groups, and Lie Algebras

Abstract

This chapter is an introduction to manifolds, Lie groups, and Lie algebras.

Jean Gallier

Chapter 19. Basics of the Differential Geometry of Curves

Abstract

In this chapter we consider parametric curves, and we introduce two important invariants, curvature and torsion (in the case of a 3D curve).

Jean Gallier

Chapter 20. Basics of the Differential Geometry of Surfaces

Abstract

The purpose of this chapter is to introduce the reader to some elementary concepts of the differential geometry of surfaces. Our goal is rather modest: We simply want to introduce the concepts needed to understand the notion of Gaussian curvature, mean curvature, principal curvatures, and geodesic lines. Almost all of the material presented in this chapter is based on lectures given by Eugenio Calabi in an upper undergraduate differential geometry course offered in the fall of 1994. Most of the topics covered in this course have been included, except a presentation of the global Gauss–Bonnet–Hopf theorem, some material on special coordinate systems, and Hilbert’s theorem on surfaces of constant negative curvature.

Jean Gallier

Chapter 21. Appendix

Abstract

This appendix covers two topics. First, we prove that hyperplanes are precisely the kernels of nonzero linear forms. Second, we review the definitions of metric spaces and normed vector spaces.

Jean Gallier

Backmatter

Titel: Geometric Methods and Applications
verfasst von: Jean Gallier
Verlag: Springer New York
Electronic ISBN: 978-1-4419-9961-0
Print ISBN: 978-1-4419-9960-3
DOI: https://doi.org/10.1007/978-1-4419-9961-0