# Complexity of Finding Largest Set of Intersecting Convex Polytopes

I have a set of $$n$$ convex polytopes, and I wish to find the largest subset of those polytopes that shares at least one point in common. I think that this problem should be NP-hard, but I am struggling to find a reduction and I can't find any relevant literature on the subject. Can anyone help me with a reduction or point me towards something I can read about? Thanks!

• Is your question about polytopes (i) in three-dimensional space, (ii) in Euclidean space with fixed dimension, or (iii) in Euclidean space where the dimension is part of the input? – Gamow Jun 20 '19 at 11:25
• Euclidean space with fixed dimension, thanks for helping me clarify. – Magdalen Dobson Jun 20 '19 at 11:59

Suppose that the dimension $$d$$ of the Euclidean space is fixed, and that the input consists of $$n$$ convex polytopes in $$\mathbb{R}^d$$ that altogether have $$p$$ facets.
Let $$h_1,\ldots,h_p$$ denote the supporting hyperplanes for the $$p$$ facets of the input polytopes. The arrangement of $$h_1,\ldots,h_p$$ is the decomposition of $$\mathbb{R}^d$$ into connected open cells of dimensions $$0,1,\ldots,d$$. It is well-known that the arrangement has combinatorial complexity $$O(p^d)$$ and that it can be computed in time $$O(p^d)$$; see for instance
So you may compute the arrangement in polynomial time $$O(p^d)$$, and then compute for every cell $$C$$ in the arrangement the number $$x(C)$$ of input polytopes that contain $$C$$. The maximum of all these numbers $$x(C)$$ yields the answer to your question.