<p>Suppose that the dimension <span class="math-container">$d$</span> of the Euclidean space is fixed, and that the input consists of <span class="math-container">$n$</span> convex polytopes in <span class="math-container">$\mathbb{R}^d$</span> that altogether have <span class="math-container">$p$</span> facets.</p>

<p>Let <span class="math-container">$h_1,\ldots,h_p$</span> denote the supporting hyperplanes for the <span class="math-container">$p$</span> facets of the input polytopes. The arrangement of <span class="math-container">$h_1,\ldots,h_p$</span> is the decomposition of <span class="math-container">$\mathbb{R}^d$</span> into connected open cells of dimensions <span class="math-container">$0,1,\ldots,d$</span>. 
It is well-known that the arrangement has combinatorial complexity <span class="math-container">$O(p^d)$</span> and that it can be computed in time <span class="math-container">$O(p^d)$</span>; see for instance</p>

<blockquote>
  <p>Chapter 28 <em>"Arrangements"</em> by D. Halperin and M. Sharir,<br>
  in Handbook of Discrete and Computational Geometry (edited by J.E. Goodman, J. O'Rourke, and C.D. Tóth)<br>
  <a href="https://www.csun.edu/~ctoth/Handbook/chap28.pdf" rel="noreferrer">https://www.csun.edu/~ctoth/Handbook/chap28.pdf</a></p>
</blockquote>

<p>So you may compute the arrangement in polynomial time <span class="math-container">$O(p^d)$</span>, and then compute for every cell <span class="math-container">$C$</span> in the arrangement the number <span class="math-container">$x(C)$</span> of input polytopes that contain <span class="math-container">$C$</span>.
The maximum of all these numbers <span class="math-container">$x(C)$</span> yields the answer to your question.</p>

CC BY-SA 4.0
2019-06-20T13:23:56.503Z
2019-06-20T13:23:56.503Z
Gamow
<p>I have a set of <span class="math-container">$n$</span> 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!</p>

CC BY-SA 4.0
2019-06-20T11:25:12.063Z
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
CC BY-SA 4.0
2019-06-20T11:59:39.377Z
Euclidean space with fixed dimension, thanks for helping me clarify.
Magdalen Dobson
<np-hardness><linear-programming><polytope>
Complexity of Finding Largest Set of Intersecting Convex Polytopes
Magdalen Dobson
# Complexity of Finding Largest Set of Intersecting Convex Polytopes

(Asked by: username_0 on 2019-06-19)

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!

**Tags:** np-hardness, linear-programming, polytope
> **Comments:**
> **username_1**: 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?  
> **username_0**: Euclidean space with fixed dimension, thanks for helping me clarify.  

---

## 1 answers

### Answer by username_1 on 2019-06-20. Score: 6 | Accepted answer

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.


---

