Polytopes and Polyhedra
Polytopes may be defined as the convex hull of finitely many points in n-dimensional space ℝ n . They are fundamental objects in computational geometry. When studying polytopes, it soon becomes apparent that the proof of seemingly obvious properties often
- PDF / 589,043 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 79 Downloads / 185 Views
Polytopes and Polyhedra
Polytopes may be defined as the convex hull of finitely many points in n-dimensional space Rn . They are fundamental objects in computational geometry. When studying polytopes, it soon becomes apparent that the proof of seemingly obvious properties often requires further clarification of the basic underlying geometric structures. An example of this is the major result that polytopes can also be represented as the intersection of finitely many affine half-spaces. In this chapter the geometric foundations of polytopes and unbounded polyhedra will be presented from a computational viewpoint.
3.1 Definitions and Fundamental Properties Definition 3.1 A set P ⊆ Rn is a polytope if it can be expressed as the convex hull of finitely many points. A k-dimensional polytope is called a k-polytope. The convex hull of k + 1 affinely independent points is a k-simplex. A 0-dimensional polytope is just a point, a 1-polytope is a line segment and the 2-dimensional polytopes are precisely the convex polygons. We adopt the convention that the empty set is a polytope of dimension −1. See Fig. 3.1 for some examples. From an analytical viewpoint, a polytope is a closed and bounded, and hence compact, subset of Rn . Polytopes in lower dimensions illustrate neither the diversity of polytopes nor the depth of higher dimensional polytope theory. We now introduce the reader to some examples of polytopes which will be useful in the following sections. The standard cube Cn is the convex hull of the 2n points which have ±1coordinates. If we denote the standard basis vectors in Rn by e(1) , . . . , e(n) , then we can express the cross-polytope as the convex hull of the 2n points ±e(1) , . . . , ±e(n) . The 3-dimensional cross-polytope is the regular octahedron. The cyclic polytopes form an important class of polytopes with extremal properties. These properties will be discussed in further detail in Section 3.5. M. Joswig, T. Theobald, Polyhedral and Algebraic Methods in Computational Geometry, Universitext, DOI 10.1007/978-1-4471-4817-3_3, © Springer-Verlag London 2013
19
20
3
Polytopes and Polyhedra
Fig. 3.1 Every 2-simplex is a triangle and every 3-simplex in R3 is a (generally irregular) tetrahedron. The right hand picture shows a 3-polytope in R3
Definition 3.2 The moment curve μn in Rn is defined as μn : R → R n ,
T τ → τ, τ 2 , . . . , τ n .
A polytope Z ⊆ Rn is called cyclic if Z is the convex hull of points of the moment curve. For n = 2 the moment curve is the standard parabola τ → (τ, τ 2 )T . Any cyclic 2-polytope that is defined as the convex hull of m ≥ 3 points is a convex m-gon. This is independent of the specific choice of the m points on the curve μ2 . It is easy to verify that the image of a polytope under an affine transformation is again a polytope (of the same dimension). Definition 3.3 An affine automorphism of a polytope P ⊆ Rn is an affine transformation of Rn that maps P onto itself. The set of all affine automorphisms of a polytope is a group with respect to composition. The size o
Data Loading...
