Algorithms and Parallel Computing

11.4 THE FACETS AND VERTICES OF

A point p ∈ lies on the kth facet (or surface) of the upper hull if it satisfies the equation

(11.16)

This facet is of dimension 2 (i.e., n − 1). We can generalize by saying that multiplying the point p by a matrix of rank 1 results in the set of points that lies on a facet of dimension 1 less than n, the dimension of . Similarly, a point p ∈ lies on the kth facet of the lower hull if it satisfies the equation

(11.17)

We can extend the above argument and find all the points that satisfy two upper hull boundary conditions. Let us choose the two boundary conditions Ψ₁ and Ψ₂. Point p ∈ lies on the 1-2 facet of the upper hull when it satisfies the equation

(11.18)

This facet is of dimension 1 (i.e., n − 2) since Ψ₁ ≠ Ψ₂ by choice, which produces a ...