# Upper bound on number of vertices in intersection (and union) of simplices

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

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.

• what is this complexity? The intersection of $n$ tetrahedra in $\mathbb{R}^3$ has $O(n)$ faces, thus $O(n)$ vertices. – Fedor Petrov May 4 '19 at 13:21
• 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? – Joseph O'Rourke May 4 '19 at 13:35
• we talk about different things: you about union, me about intersection) – Fedor Petrov May 4 '19 at 14:17
• $S_i$ are simplices, their intersection is convex, right? – Fedor Petrov May 4 '19 at 14:51
• @FedorPetrov: Apologies for misunderstaning you, and for not noticing that the OP asked for the complexity of the hull of the union. – Joseph O'Rourke May 4 '19 at 17:57