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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .