Complete case

We follow these conventions, with $d=n$ and $Σ$ non-rational non-simplicial a priori. We use the standard inner product. By locally we mean for each compartment.

Conventions and notations

Let $P, Q$ be $Σ$-compartmentalized polytopes, $K,L$ $Σ$-compartmentalized convex bodies. $C$ is a full dimensional strictly convex cone.

Summarizing basic properties

To see the proofs, overlay the link, read, and then click the link.

We systematically study the links between :

• (c) compartmentalized I : $∀ x ∈ P ∩ C, (x - C^∨) ∩ C ⊆ P$,
• (c*) co-compartmentalized : $∀ x ∈ C, (∀ u ∈ C, ⟨u,x⟩ ≤ \max_P ⟨u,⋅⟩) ⇒ x ∈ P$.
• (max-c) max-compartmentalized II : $∀ u ∈ C, \mathrm{argmax}_P ⟨u,⋅⟩ ∩ C ≠ ∅$,

and the following properties

• (∋0) P contains zero

In the following cases, $Σ$ being complete :

• (*) any $Σ$,

• (+) $Σ$ positive,

• (<) $Σ$ acute-angled.

• (△) P simplicial

In particular via the followings operations :

• (⊞) Minkowski sums,
• (∩) intersection,
• (⊍) convex hull,
• (∨) polarization.

Study of the fans properties :

(+) ⇐ (<) ⇒ (△)
(+) ⇏ (△)
(+) is stable by : subfaces star tropical modification
(<) is stable by : subfaces star tropical modification
(△) is stable by : subfaces star tropical modification

Case (*)

• Case (c) :
  • (∋0)
  • ⇐⇒ (c*)
  • (max-c)
  • (∩) → (c)
  • (∨): not clear what it means if does not contain zero…
  • rest: cf. case (+)
• Case (max-c)
  • ⇒ (c) ❓
  • (⊞) → (max-c)
  • (∩)
  • (⊍) → (max-c)
  • (∨)

Case (+)

• Case (c) :
  • (∋0)
  • (max-c)
  • (⊍) ↛ (c)
  • (⊞) ↛ (c)

Lemmas

Lemma “Characterization of acute-angled cones via orthogonal projections” 1

For $C$ a cone, the followings are equivalent.

1. the orthogonal projection of $C$ on $N_η$ where $η$ is a facet of $C$ is included in $C$,
2. the angle between two facets is at most $90^∘$,

Proof

• 2. ⇒ 1. because you take a facet $η$ and a facet $σ$ of $η$. Then $H = ℝσ + η^⟂$ is a support hyperplane of $C$. Indeed, this is obvious if you take the cone $C/σ$.
• 1. ⇒ 2. quite clear: take two adjacent facets $η, η'$ whose intersection is some $σ$. Then, projecting along $σ$, we get the result.

Lemma “Faces of acute-angled cones are acute-angled” 2

(<) stable by subfaces

Proof (🔴)

It suffices to check it for facets. Assume there is a facet $η$ diamond $τ ≺ σ,σ' ≺ η$ with $n_{η/σ}⋅n_{η/σ'} > 0$. The lattice above $τ$ is the one of a polygon. Take two consecutive facets $ζ,ξ$ apart from $η$ containing $τ$. Let $π$ be the orthogonal onto $η$. Let us prove that $n_{C/ζ}⋅n_{C/ξ} > 0$. We have $$n_{C/ζ} = π(n_{C/ζ}) + ⟨n_{C/η},n_{C/ζ}⟩n_{C/η}$$ hence $$n_{C/ζ}⋅n_{C/ξ} = π(n_{C/ζ})⋅π(n_{C/ξ}) + ⟨n_{C/η},n_{C/ζ}⟩ × ⟨n_{C/η},n_{C/ξ}⟩.$$ We just have to prove that the three inner products are nonnegative, and not all zeroes. For the two last ones, the non-negativity comes from point 2, and they cannot be both zero, since otherwise $ξ ∩ ζ$ would be a codimension 1 cone containing $τ$ and parallel to $η$, that is would be included in $ℝη$ which is clearly impossible. For the first scalar product, $⟨n_{C/ζ},⋅⟩$ is nonnegative on $C$, hence on $η$. So $π(n_{C/ζ}) ∈ η_η^∨ = ℝ_{≥0}n_{η/σ} + ℝ_{≥0}n_{η/σ'}$ (the dual of $η$ in its own tangent space). Hence, $π(n_{C/ζ})⋅π(n_{C/ξ}) ≥ 0$.

Lemma “Acute-angled cones are simplicial” 3

(<) ⇒ (△)

Proof

By induction, all the facets are simplicial cones. Moreover, by induction, all proper star fans are simplicial. Hence, the link of $0$ in $C$ is a simple and simplicial polytope. Hence it is a simplex, or of dimension 2. It remains to deal with the case $\dim(C) = 3$. This follows from the fact that the sum of the angles of a $s$-gon on $𝕊^2$ is greater than $180^∘⋅(s-2)$. Hence, if all the angles are at most $90^∘$, then $s=3$.

Lemma “Acute-angled cones are positive” 4

(<) ⇒ (+)

Proof

Take $e_ρ$ and $e_{ρ'}$ in two rays $ρ, ρ'$ in the same cone. By Lemma “Acute-angled cones are simplicial” 3, both rays belong to the same 2-cone, which is acute-angled by @lem:acute-subface. Hence $e_ρ⋅e_{ρ'} ≥ 0$.

Lemma “Compartmentalized structures are co-compartmentalized” 5

3. ⇒ (c*)

Proof

Let $C ∈ Σ$ and consider $P ∩ C$. Let $η$ be a facet of $P ∩ C$ which is not in a facet of $C$.

If $n_{P/η} ∉ C$, then there exists $ρ ∈ C^∨$ such that $⟨e_ρ, n_{P/η}⟩ < 0$. Hence $x - ε e_ρ$, for some $x$ in the interior of $η_η$, does not belong to $P$, so $P$ is not compartmentalized.

Hence, the outer normal vectors to the facets of $P ∩ C$ are either in $C$, or in a ray of $C^∨$. Now, $$P ∩ C = \{x \mid ⟨e_ρ, x⟩ ≥ 0, ∀ ρ ∈ C_1 \text{ and } ⟨u,x⟩ ≤ \max_P ⟨u,⋅⟩, ∀ u ∈ C \} = \{x ∈ C ∣ ⟨u,x⟩ ≤ \max_P ⟨u,⋅⟩, ∀ u ∈ C \}.$$ So $P ∩ C$ verifies the condition of $(c*)$.

(Counter-)examples

Example “A compartmentalized structure not containing zero” 1

Example “A positive fan which is not acute-angled” 2

Take the fan of orthants in $ℝ^3$. Blow-up the positive orthant in the barycenter. span of $(1,0,0)$, $(0,1,0)$, $(10,10,1)$.

Example “A compartmentalized structure which is not max-compartmentalized” 3

Take the fan in Example “A positive fan which is not acute-angled” 2 with the polytope $[0;1]×\{0\}×\{0\}$.

Example “Two compartmentalized structures whose Minkowski sum and convex hulls are not compartmentalized” 4

Take the polytope in Example “A compartmentalized structure which is not max-compartmentalized” 3 and another one which is $\{0\}×[0;1]×\{0\}$. Then both their sums and their convex hull are not compartmentalized.

Archive

Basic properties (of complete compartmentalized structures obsolete)

Example 5

Wrong: $0 ∈ K$.

Proof

Lemma 6 (A cone always intersects its dual)

Let $C$ be a cone. Then $C ∩ C^∨$ is a full-dimensional cone.

Proof

Let $e$ a unit vector in $C$ maximizing the minimum of $⟨e, C ∩ 𝕊^{n-1}⟩$. Then $e$ is in the interior, otherwise we can add an normal inner vector and we get something better. $C' = C ∩ e^⟂$ is strictly convex. If it is $0$, then we are done. Otherwise, take $v$ in the interior of $C'^∨$. Then $(e+εv)/‖e+εv‖$ is strictly better than $e$. Indeed, the maxima are all obtained in the same open half-space of $v^⟂$ (they are in $(e^⟂)_{≤0}$ and then look at the segment between them and $e$).

Lemma 7

Let $C$ be a cone. Then the following are equivalent

1. the orthogonal projection of $C$ on $N_η$ where $η$ is a facet of $C$ is included in $C$,
2. the angle between two facets is at most $90^∘$,
3. any face verifies 1.,
4. any star fan verifies 2.,
5. star fan around rays verifies 2.,

and they strictly imply

1. for any $x,y ∈ C$, $⟨x,y⟩ ≥ 0$,
2. $C$ is simplicial.

Proof

• 2. ⇒ 1. because you take $η$ and a facet $σ$ of $η$. Then $H = ℝσ + η^⟂$ is a support hyperplane of $C$. Indeed, size is obvious if you take the cone $C/σ$.
• 1. ⇒ 2. quite clear: take two adjacent facets $η, η'$ whose intersection is some $σ$. Then, projecting along $σ$, we get the result.
• 3. ⇒ 1. obvious.
• 2. ⇔ 4. ⇔ 5., star fans preserve facets angles,
• 1. ⇏ 2. take the span of $(1,0,0)$, $(0,1,0)$, $(10,10,1)$, a. is true since it is true on rays, but the projection of $(101,0,0)$ on the opposite facet is equal to $(100,0,10) = 10⋅(10,10,1) - 100⋅(0,1,0)$.
• 2. ⇏ 2. take the span of $(1,0)$ and $(-1,1)$.
• ❗1. & 2. ⇒ 3. It suffices to check it for facets. Assume there is a facet $η$ diamond $τ ≺ σ,σ' ≺ η$ with $n_{η/σ}⋅n_{η/σ'} > 0$. The lattice above $τ$ is the one of a polygon. Take two consecutive facets $ζ,ξ$ apart from $η$ containing $τ$. Let $π$ be the orthogonal onto $η$. Let us prove that $n_{C/ζ}⋅n_{C/ξ} > 0$. We have $$n_{C/ζ} = π(n_{C/ζ}) + ⟨n_{C/η},n_{C/ζ}⟩n_{C/η}$$ hence $$n_{C/ζ}⋅n_{C/ξ} = π(n_{C/ζ})⋅π(n_{C/ξ}) + ⟨n_{C/η},n_{C/ζ}⟩ × ⟨n_{C/η},n_{C/ξ}⟩.$$ We just have to prove that the three inner products are nonnegative, and not all zeroes. For the two last ones, the non-negativity comes from point 2, and they cannot be both zero, since otherwise $ξ ∩ ζ$ would be a codimension 1 cone containing $τ$ and parallel to $η$, that is would be included in $ℝη$ which is clearly impossible. For the first scalar product, $⟨n_{C/ζ},⋅⟩$ is nonnegative on $C$, hence on $η$. So $π(n_{C/ζ}) ∈ η_η^∨ = ℝ_{≥0}n_{η/σ} + ℝ_{≥0}n_{η/σ'}$ (the dual of $η$ in its own tangent space). Hence, $π(n_{C/ζ})⋅π(n_{C/ξ}) ≥ 0$.
• ❗2. ⇒ b. By induction, all the facets are simplicial cones. Moreover, by induction, all proper star fans are simplicial. Hence, the link of $0$ in $C$ is a simple and simplicial polytope. Hence it is a simplex, or of dimension 2. It remains to deal with the case $\dim(C) = 3$. This follows from the fact that the sum of the angles of a $s$-gon on $𝕊^2$ is greater than $180^∘⋅(s-2)$. Hence, if all the angles are at most $90^∘$, then $s=3$.

Here is an alternative proof for the dimension 3 case. Take the dual cone $C^∨$. Take a vector $e$ in the interior of $C^∨$ such that $C^∨ ∩ e^⟂ = {\underline{0}}$. Such a vector exists by Lemma 6 (A cone always intersects its dual). Point 2. is equivalent to requiring $e_ρ⋅e_{ρ'} ≤ 0$ whenever $ρ ∧ ρ' ≠ 𝟏$. Project orthogonally the $e_ρ$ on $H$. Let us call the projection map $π$. Then $π(e_ρ)⋅π(e_{ρ'}) < e_ρ⋅e_{ρ'} ≤ 0$ (⋆) since both vectors lies in the open half-space $H_{>0}$. If $π(C^∨) ≠ H$, then clearly (⋆) cannot holds. Hence, the projection of $C^∨$ induces a complete fan of dimension two with only strictly obtuse angles. This can only have three facets.

There seems to be no much acute-angled fans. In article, Theorem C state that no complete fan strictly acute-angled of dimension 5 of higher exists. Maybe a reference?

We say that a cone $C$ is acute-angled if any of the previous statement holds. We say that a fan is acute-angled if its cones are.

A cone is positive if $C ⊆ C^∘$.

Example 6 (Positive cone not in orthant)

Take the cone $C$ spanned by the permutations of $(7,4,-1)$. Then $⟨x,y⟩ > 0$ for any $x,y ∈ σ$ but $C$ cannot be mapped orthogonally inside the positive orthant. Indeed, take an orthant cone $C ⊆ O ⊆ C^∨$. Then three orthogonal vectors $e, f, g$ in $C^∨$. Then ❓

❓same question when simplicial

Example 7 (A compartmentalized structure locally but not globally convex)

Wrong: Any body $T$ $Σ$-compartmentalized whose compartments are convex is convex.

Proof

Take $T = [0;1]×[0;1] + [-1;0]×[-1;0]$. It is anti-blocking and locally convex but not globally.

Lemma 8

For each $ρ$, $\mathrm{argmax}_P e^*_ρ(x) ∈ ρ$.

Proof

Otherwise, let $x$ be the argmax on $ρ$ and $y$ be the global argmax. Then, $εy+(1-ε)x$ belongs to a cone $σ ≻ ρ$ for $ε > 0$ small enough.

Question 1

Are compartmentalized polytopes stable by Minkowski sum?

Answer

Question 2

Question 3

Question 4