Computation of Convex Hulls
When referring to “computation of convex hulls” we understand this as the task of computing the \(\mathcal {H}\) -representation of the convex hull of a given finite point set V⊆ℝ n . Depending on the desired application, one might also need to compute al
- PDF / 269,858 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 88 Downloads / 152 Views
Computation of Convex Hulls
When referring to “computation of convex hulls” we understand this as the task of computing the H-representation of the convex hull of a given finite point set V ⊆ Rn . Depending on the desired application, one might also need to compute all faces, a description of the face lattice or other geometric information.
5.1 Preliminary Considerations We begin with two simple results. First, Algorithm 5.1 immediately gives a trivial convex hull algorithm, which is, unfortunately, inefficient. Theorem 3.9, together with the fact that the computed half-spaces define facets, shows that the algorithm is correct. The assumption that the affine hull is fulldimensional is not necessary. Without it, the algorithm can simply be applied to the affine hull of the input.
Algorithm 5.1: A trivial convex hull algorithm Input: Finite point set V ⊆ Rn with dim aff V = n. Output: Finite set of half-spaces {H1+ , . . . , Hm+ } such that m + i=1 Hi = conv V . 1 H←∅ 2 foreach n-element subset W ⊆ V with dim aff W = n − 1 do 3 H ← aff W 4 if V ⊆ H + then 5 H ← H ∪ {H + } 6 else 7 if V ⊆ H − then 8 H ← H ∪ {H − } 9
return H
M. Joswig, T. Theobald, Polyhedral and Algebraic Methods in Computational Geometry, Universitext, DOI 10.1007/978-1-4471-4817-3_5, © Springer-Verlag London 2013
65
66
5
Computation of Convex Hulls
Secondly, the dual problem, i.e., computing a V-representation of a polytope from its H-representation is, by polarity, algorithmically equivalent to the convex hull problem: Theorem 5.1 The problem of computing the V-representation of a polytope from its H-representation can be reduced to the convex hull problem and vice versa. + Proof Let P = m i=1 Hi be given in the H-representation. Via the linear programs from Example 4.3 and Exercise 4.4 we can compute the affine hull A = aff P and a point from the relative interior x in P = P ∩ A. We can thus assume that P is full-dimensional. We can also assume that the origin is an interior point, since we can otherwise apply our computations to A and translate by −x. (i) (i) + + Since 0 ∈ int P , there exist h(i) k such that Hi = [1 : h1 : · · · : hn ] . We now examine the polar polytope which has, according to Theorem 3.28, the Vrepresentation P ◦ = conv{h(1) , . . . , h(m) }. Using a convex hull algorithm we can (j ) (j ) obtain an H-representation P ◦ = kj =1 [1 : v1 : · · · : vn ]+ . Looking at the polar polytope of P ◦ and using Theorem 3.29 we get P = P ◦◦ = conv v (1) , . . . , v (k) . The reverse direction is similar. In fact, it is easier since it is not necessary to use the linear programming techniques used above. In the dual representation of the convex hull problem it becomes clear that the problem can be viewed as a far-reaching generalization of the linear optimization problem: While linear optimization aims at computing one specific vertex of an Hpolytope (defined by a linear objective function), the dual convex hull algorithm computes all vertices of P . Note that the existence of cyclic polytopes of dimension n with m ver
Data Loading...
