Let $S_1, \dots, S_k \subset \mathbb{R}^n$ be a set of (non-regular) simplices. Let $m_i$ indicate the number of vertices of simplex $S_i$ (we do not assume it is equal to $n-1$).

Is there a simple upper bound on the maximum number of vertices of the intersection $\bigcap_i S_i$, stated in terms of the set $\{ m_i\}_{i=1..k}$?

What about the maximum number of vertices of the convex hull of the union, $\mathrm{Conv}\big(\bigcup_i S_i\big)$?

(Cross-posting from math.SE)


1 Answer 1


In the literature, the dimension is usually $d$ (rather than your $n$), and the number objects is $n$ (rather than your $k$).

The intersection of $n$ halfspaces in dimension $d$ can have $n^{\lfloor d/2 \rfloor}$ vertices. This is achieved by the dual of cyclic polytopes. See the MO question How many vertices can a convex polytope have?.

For the union, although the union itself can be complicated, the convex hull of the union is not: All the vertices of the simplices could fall on the hull. So the union can have at most $O(n d)$ vertices, because each of the $n$ simplices can have at most $d+1$ vertices.

  • $\begingroup$ what is this complexity? The intersection of $n$ tetrahedra in $\mathbb{R}^3$ has $O(n)$ faces, thus $O(n)$ vertices. $\endgroup$ Commented May 4, 2019 at 13:21
  • $\begingroup$ In the plane, the union of $n/2$ thin horizontal triangles with $n/2$ thin vertical triangles produces a grid-like object with $\Omega(n^2)$ vertices. Perhaps we are using the word "vertices" differently? $\endgroup$ Commented May 4, 2019 at 13:35
  • $\begingroup$ we talk about different things: you about union, me about intersection) $\endgroup$ Commented May 4, 2019 at 14:17
  • $\begingroup$ $S_i$ are simplices, their intersection is convex, right? $\endgroup$ Commented May 4, 2019 at 14:51
  • $\begingroup$ @FedorPetrov: Apologies for misunderstaning you, and for not noticing that the OP asked for the complexity of the hull of the union. $\endgroup$ Commented May 4, 2019 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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