How to find the minimum number of hyperplanes to define a convex hull?

Question

I have the following problem:

I have a convex hull $\Omega$ defined by a set of n-dimensional hyperplanes $S = [(n_1,d_1), (n_2,d_2),...,(n_k,d_k)]$ such that a point $p \in \Omega$ if $n_i^T p \geq d_i \quad \forall (n_i,d_i) \in S $. Now I have a "joining" hyperplane $(n_{k+1},d_{k+1})$ and I want to know if this hyperplane "modifies the shape" of the convex hull and in that case, which hyperplanes of $S \bigcup (n_{k+1},d_{k+1})$ are not necessary anymore because they become redundant.

Trivial example with one dimension:

My convex hull is described by the inequality $ 3 \leq x \leq 5$ so

$S = [(1,3),(-1,-5)]$

The joining hyperplane is the inequality $ x \geq 4$ so the resulting convex hull should be $ 4 \leq x \leq 5$

$S = [(1,4),(-1,-5)]$

returning $(1,3)$.

Now I would like the same thing generalized for n-dimensions. I can get algorithms till 3 dimensions but they are not generalized.

Do you have any hints or pointers on how I can find a solution to this problem?

p.s. I apologize for the sloppy description, I am not a mathematician. Please feel free to ask for more details.

Kind regards.

Answer 1

If you search for detection of redundant constraints in linear programming you will find many hits, including one to an MO question, "Detection of Redundant Constraints." One source paper is

J. Gondzio. Presolve analysis of linear programs prior to applying an interior point method. OSRA Journal on Computing, 9(1):73–91, 1997. Link here.

Google Scholar will permit you to locate the 77 papers that cite this. Detecting redundant constraints in linear programming is by now a standard topic, and is in fact incorporated into most LP solvers.

To respond to Gerhard's comment:

However, it is known that the problem of determining whether or not a linear matrix inequality constraint is redundant or not is NP-complete, in general.

This from "Identifying Redundant Linear Constraints in Systems of Linear Matrix Inequality Constraints," Jibrin & Stover, 2007. PDF download

Answer 2

There are two ways to represent convex polytopes: as the convex hull of its vertices, or as the intersection of the half-spaces whose boundaries contain the faces. If you store both of these representations, checking if a new constraint is redundant is easy: if all current vertices satisfy it, then so do all points in the convex hull. Now, the problem is (a) how large is the vertex representation? -- in general it can be exponential with the number of constraints -- and (b) how to update the vertex representation in case a new constraint is relevant. It might be more efficient in your situations, where constraints are added one by one, to store the vertex representation, but it might not, depending on the situation.

P.S. Also note that by duality, the problem you describe is equivalent to checking whether a new point lies in the convex hull of a set of old points. So as you search the literature, you might have more luck finding the dual version treated.

Answer 3

See this question, in particular Ken Clarkson's answer.