Introduction and Overview
This book studies geometry methodically from an analytical, i.e., coordinate-based, viewpoint. In many settings this approach simplifies the computer representation of geometric data. We shall not confine ourselves to linear problems. This is not only app
- PDF / 301,494 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 1 Downloads / 179 Views
Introduction and Overview
This book studies geometry methodically from an analytical, i.e., coordinate-based, viewpoint. In many settings this approach simplifies the computer representation of geometric data. We shall not confine ourselves to linear problems. This is not only appealing from a theoretical viewpoint, it is also practically motivated by advances in computer algebra and the availability of fast computer hardware. In Chapter 2 we will lay some mathematical foundations. First, we will introduce the language of projective geometry, which is very well suited for many geometric applications. Since this is not usually covered in standard introductory courses in mathematics, we briefly discuss the central concepts of projective spaces and projective transformations. We will also introduce the notion of convexity in this chapter. Our analytical approach motivates the structure of this book. It is centered around questions about algorithms which solve systems of equations and their increasingly complex variations with regard to the required mathematical tools.
1.1 Linear Computational Geometry Most algorithms described in this book are based on Gaussian elimination, a core topic in any linear algebra course. In geometric language Gaussian elimination is a procedure which takes a set of affine hyperplanes, H1 , . . . , Hk , in the vector space K n as input, where K is an arbitrary field. If A = H1 ∩ · · · ∩ Hk
(1.1)
the output can be an (affine) basis for A, or simply its dimension. Our foray through computational geometry begins with the real numbers and the transition from equalities to inequalities. Consider for every hyperplane n n Hi = x ∈ R : aij xj = bi j =1
M. Joswig, T. Theobald, Polyhedral and Algebraic Methods in Computational Geometry, Universitext, DOI 10.1007/978-1-4471-4817-3_1, © Springer-Verlag London 2013
1
2
1 Introduction and Overview
Fig. 1.1 An example of a bounded polyhedron in R3 . This particular polyhedron is a polytope which is dual to a zonotope. The belt-like strip in the middle has several very thin facets
the closed half-space
Hi+
= x∈R : n
n j =1
aij xj ≥ bi .
The intersection P = ki=1 Hi+ defines a (convex) polyhedron (see Fig. 1.1 for an example in R3 ). Polyhedra are fundamental to computational geometry and linear optimization. In higher dimensions, the combinatorial variety of polyhedra is considerably larger than that suggested by lower dimensional images, such as Fig. 1.1. One of the fundamental questions when determining the complexity of many algorithms is, what is the maximum number of vertices that a polyhedron defined by k linear inequalities can have? This question was first answered in 1970 by the Upper-bound Theorem. The proof (in a somewhat weaker formulation, see Theorem 3.46) and the explanation of the underlying geometric structure is the first goal of this book. This result is particularly important for computational geometry because we can use it to obtain complexity estimates for several algorithms. In Chapter 3 we systematicall
Data Loading...
