Suppose I have $k$ $n$-dimensional polytopes $P\_1,\ldots,P\_k$, each explicitly specified as the intersection of a collection of hyperplanes. If there was a point $p \in \mathbb{R}^n$ that lay in the intersection of all of these polytopes ($p \in P\_1 \cap \ldots \cap P\_k$), I could efficiently find it by solving a linear program. Unfortunately, I have no guarantee that my polytopes have non-empty intersection. However, someone has promised me that there exists a point $p$ that lies in at least $2/3$ of my polytopes: that is, there exist indices $i\_1,\ldots,i\_{2k/3}$ such that:
$$p \in P\_{i\_1} \cap \ldots \cap P\_{i\_{2k/3}}$$


Does there exist an efficient algorithm (running in time polynomial in k and n) that can find such a point?



Finding a point that lies in a majority of polytopes
This problem is clearly in NP (guess which polytopes) and becomes NP-complete if we replace $2/3$ with $1/2$ and make it a decision problem, dropping the promise that such a $p$ exists. In particular we can reduce integer programming feasibility to this problem.


Say we wish to determine whether $Ax = b$ has a solution $x$ which is a zero-one vector. We can define $k = 2n$ polytopes $P\_i^j = \{x \mid x\_i = j, Ax = b, 0\leq x\leq 1\}$ for integers $1\leq i\leq n$ and $0\leq j\leq 1$. A zero-one solution of $Ax=b$ is the same as a point which lies in $l = n = k/2$ of these polytopes.


I imagine there is a simple reduction showing that the problem is still hard if we use the fraction $2/3$ (or any other fixed fraction) instead of $1/2$. But I'm guessing that you just gave $2/3$ as an example so I haven't thought about it. Similarly I am guessing that the problem is still hard if you somehow know that such a $p$ exists and merely want to find one, but I haven't thought of how to show this either.


