Page 31 - Tequio 11
P. 31
On some polytopes in phylogenetics/Hoessly/27-40 29
Figure 2.
Two different binary X-trees on the tree T of figure 1.
2.2 Polytopes
Polytopes are seemingly simple geometric objects with flat sides. They appear as convex hulls of a finite set
of points in Euclidean space (like, e.g., the plane ℝ or 3-dimensional space ℝ ), and exhibit a rich variety of
*
A
combinatorial structures (Ziegler, 1995). The convex hull of a set of points { - , ⋯ , D } ⊂ ℝ is defined as
/
D D
conv{ - , ⋯ , D }: = { ∈ ℝ ∣ = N P P , N P = 1, P ≥ 0}
/
PQ- PQ-
A polytope is a convex hull of a finite set of points. Well-known examples include two-dimensional polytopes
that are convex polygons like the square (cf. Figure 3). The dimension of a polytope is the dimension of the
smallest Euclidean space which could contain it. As an example, the square of figure [fig_octa] has dimension
two. A face of a polytope is any intersection of the polytope with a half-space such that none of the interior
points of the polytope lie on the boundary of the half-space. Any face of a polytope is a polytope itself. Some
faces have a special name, faces of dimension 0,1 and dim() − 1 are called vertices, edges and facets.
Moreover, the faces of polytopes can be ordered by inclusion, giving the poset of faces. A rougher invariant are
Y
Y
its face numbers , , … , [\](Y) , which are defined as
= #{ − dimensional faces of }.
Y
P
Putting all the face numbers together gives a convenient way of writing them as the so-called f-vector
( , , … , Dg- ), where = dim(). Note that convex polytopes may equivalently be defined as an intersection
Y
Y
of a finite number of half-spaces, corresponding to the so-called hyperplane description, see, e.g., (Ziegler,
1995, §2.4).
Example 2.2. Consider the d-crosspolytope, which is defined as
j : = conv{ - , − - , ⋯ , j , − j } ⊆ ℝ ,
j
Tequio, enero-abril 2021, vol. 4, no. 11