# Efficient construction of the strict interior of a polytope.

Let $$B_\infty(x, \delta)$$ denote the set of all points within $$\delta$$ of $$x$$ in the $$L_\infty$$ norm.

For a vector in $$\mathbb{R}^n$$ and an index set $$I \subseteq \{1, ..., n\}$$ let $$x_I$$ denote the vector composed of those indices in $$I$$.

Given $$A^{\textrm{eq}} \in \mathbb{R}^{m \times n}$$, $$b^{\textrm{eq}} \in \mathbb{R}^{m}$$, $$A^{\textrm{ineq}} \in \mathbb{R}^{p \times n}$$, $$b^{\textrm{ineq}} \in \mathbb{R}^{p}$$, an index set $$I$$ (as above), and a $$\delta > 0$$ how can I efficiently (in less than exponential time) construct

$$\left\{x \in \mathbb{R}^n : A^{\textrm{eq}} \zeta = b^{\textrm{eq}}, A^{\textrm{ineq}} \zeta \le b^{\textrm{ineq}} \textrm{ for all } \zeta \textrm{ such that } \zeta_I \in B_\infty(x_I, \delta) \right\}?$$

If it is not possible to fully characterise this set, can I characterise a subset of it?

Stated geometrically, given a big polytope and some diameter $$\delta$$, how can I construct the set of points in that polytope for which it is possible to put a ball around some dimensions of that point that is also included in that polytope?

The method described in this related question allows me to ask whether a point is in this set, and it works well. I'd now like to construct the set of all points.