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)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
7
  • $\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, 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$
    – Joseph O'Rourke
    May 4, 2019 at 13:35
  • $\begingroup$ we talk about different things: you about union, me about intersection) $\endgroup$
    – Fedor Petrov
    May 4, 2019 at 14:17
  • $\begingroup$ $S_i$ are simplices, their intersection is convex, right? $\endgroup$
    – Fedor Petrov
    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$
    – Joseph O'Rourke
    May 4, 2019 at 17:57

Your Answer

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

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