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.



How to find the minimum number of hyperplanes to define a convex hull?
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](https://mathoverflow.net/questions/69662/)."
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](http://Presolve%20analysis%20of%20linear%20programs%20prior%20to%20applying%20an%20interior%20point%20method/).
> 
> 
> 


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](http://www.cefns.nau.edu/Academic/Math/researchInterests/students/sdpred_may31_07.pdf)


