5
$\begingroup$

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!

$\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 at 11:25
  • $\begingroup$ Euclidean space with fixed dimension, thanks for helping me clarify. $\endgroup$ – Magdalen Dobson Jun 20 at 11:59
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.