2
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ what is this complexity? The intersection of $n$ tetrahedra in $\mathbb{R}^3$ has $O(n)$ faces, thus $O(n)$ vertices. $\endgroup$ – Fedor Petrov May 4 '19 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$ – Joseph O'Rourke May 4 '19 at 13:35
  • $\begingroup$ we talk about different things: you about union, me about intersection) $\endgroup$ – Fedor Petrov May 4 '19 at 14:17
  • $\begingroup$ $S_i$ are simplices, their intersection is convex, right? $\endgroup$ – Fedor Petrov May 4 '19 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$ – Joseph O'Rourke May 4 '19 at 17:57

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.