Convex polyhedron with open faces Convex polyhedron $P$ is a subset of $\mathbb{R}^n$ that satisfies system of linear inequalities
\begin{align}
a_{11}x_1 + \cdots + a_{1n}x_n & \sim_1\, c_1 \\
& \vdots \\
a_{p1}x_1 + \cdots + a_{pn}x_n & \sim_p\, c_p,
\end{align}
where $\sim_i \in \{\leq,\geq\}$. It can be alternatively represented by two finite sets of generators $V, W \subseteq \mathbb{R}^n$: $$P = \text{conv}(V) + \text{cone}(W),$$ where conv(V) denotes all convex combinations of points in V and cone(W) all nonnegative linear combinations of points in W.
Now, what if we allow $\sim_i$ to be from $\{\geq,>,\leq,<\}$. Is there some similar representation in terms of generating points for such sets?
(I possess no knowledge of this area of mathematics, so I apologize if I got the terminology wrong or if this question is just plain stupid.)
 A: No.  Unfortunately, it can't even be done in the 1D case.  For instance, consider the inequalities $x > 0$ and $x < 1$.  Then $P$ is the open interval $(0,1)$.  You can't take $V = \{0,1\}$ because then conv$(V)$ is the closed interval $[0,1]$.  Taking $V$ to be any other two points between 0 and 1 would generate a conv$(V)$ that is a strict subset of $P$.
A: Seems like such polyhedra are called not necessarily closed (NNC) and are usually represented as closed polyhedra with additional dimension $\varepsilon$: every strict inequality $a_{i1}x_1 + \ldots + a_{in}x_n > c_i$ is replaced by $a_{i1}x_1 + \ldots + a_{in}x_n - \varepsilon \geq c_i$ and two additional inequalities $0 \leq \varepsilon \leq 1$ are added to the system. If we call this polyhedron $P'$, the desired polyhedron is the set $\{ (x_1,\ldots,x_n) \mid (x_1,\ldots,x_n,\varepsilon) \in P', \varepsilon > 0 \}$. Such a system of constraints can be converted to representation by generators.
Alternatively, they can be characterized directly by three sets of generators $R,P,C \in \mathbb{R}^n$, i.e. every point can be obtained as
$$\alpha_1r_1 + \ldots + \alpha_kr_k + \beta_1p_1 + \ldots + \beta_lp_l + \gamma_1c_1 + \ldots + \gamma_mp_m,$$
where $r_i \in R, p_i \in P, c_i \in C$ and $\alpha_i, \beta_i, \gamma_i \in \mathbb{R}^+$ and $\sum_{i=1}^l \beta_i + \sum_{i=1}^m \gamma_i = 1$ and there is $1 \leq i \leq l$ such that $\beta_i \neq 0$. The trick here is that points in $C$ don't have to lie within the NNC polyhedron, but its closure, and whenever they appear in the sum, there must also be point from $P$ with nonzero coefficient. This representation can easily be converted to the one mentioned above.
References:
R. Bagnara, P. M. Hill, E. Zaffanella: A New Encoding of Not Necessarily Closed Convex Polyhedra
R. Bagnara, E. Ricci, E. Zaffanella, P. M. Hill: Possibly Not Closed Convex Polyhedra and the Parma Polyhedra Library
Seems like this stuff is used mostly in static analysis/verification and is not interesting to mathematicians, maybe I should have asked on cstheory instead? Any feedback regarding the question welcome, as well as corrections regarding my misuse of terminology/notation.
