Two Related Problems of Redundancy Reduction in Data Representation by Means of Convex Polyhedra

Abstract

Two problems of data representation by means of convex polyhedra are considered. In the first problem, it is required to exclude from a finite set of points X the points that are not vertices of the convex hull of X. An algorithm based on solving a series of linear programming problems is developed. Its computational complexity is asymptotically lower than the complexity of a convex hull constructing, and it requires much less additional memory than for constructing a convex hull. The second problem consists in finding the minimal subset of inequalities in a system of linear inequalities whose solution set coincides with the solution set of the initial system. It is shown that this problem can be solved similarly to the first one, and the solution algorithm can be extended to the case of nonlinear inequalities. Randomized improved versions of both algorithms are proposed.