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!
$\begingroup$
$\endgroup$
-
$\begingroup$ 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? $\endgroup$ – Gamow Jun 20 '19 at 11:25
-
$\begingroup$ Euclidean space with fixed dimension, thanks for helping me clarify. $\endgroup$ – Magdalen Dobson Jun 20 '19 at 11:59
$\begingroup$
$\endgroup$
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
Chapter 28 "Arrangements" by D. Halperin and M. Sharir,
in Handbook of Discrete and Computational Geometry (edited by J.E. Goodman, J. O'Rourke, and C.D. Tóth)
https://www.csun.edu/~ctoth/Handbook/chap28.pdf
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.
