An Algorithm for Convex Polytopes
Donald R. Chand, Sham S. Kapur · Journal of the ACM · 1970
An algorithm, one that is economical and fast, for generating the convex polytope of a set S of points lying in an n-dimensional Euclidean space E" is described.In the existing brute force method for determining the convex hull of a set of points lying in a two-dimensional space, one computes all possible straight lines joining each pair of points of S and tests whether the lines bound the given set S. This method can easily be generalized for computing the convex hull of a set S C E", n > 2. However, it turns out that this approach is not feasible due to excessive computer run time for a set of points lying in E n when n > 3. The algorithm described in this paper avoids all the unnecessary calculations, and the convex polytope of a set S C E n is generated by systematically computing the faces from the edges of the desired convex polytope.A numerical comparison indicates that this new approach is far superior to the existing brute force technique.