1

Supposedly I have a Convex object $A$ in high dimension(Eculdian space), and I know their low dimensional projection(only look at 2 dimensions at a time) is a zonotope, how can I assert/reject $A$ is a Zonotope?

A concrete example,

$$ A = CH(\{(0, 0, 0), (1, 1, 1), (2, 3, 2), (1, 2, 1)\}) $$, $CH$ is the convex hull operation. it can be shown that if only look at the (0, 1) dimensional projection: $$ CH(\{(0, 0), (1, 1), (2, 3), (1, 2)\}) $$ is a zonotope with generators $((1, 1), (1, 2))$, how can i prove or disprove $A$ is a Zonotope.

More context:

My data has such a generating process, assume I have a sequence of finite random points $$ a_1, \cdots, a_i, \cdots, a_n. a_i \in \mathbb{R}^m_+ $$.

And I'm interested in the Convex hull of the prefix sum of such sequence: $$ B = (b_1, \cdots, b_i, \cdots, b_n) = a_1, a_1+a_2, \cdots, \sum_{j=1}^n a_j $$.

When $m = 2$, i can prove that $CH(B)$ is a union of two Zonotopes.

As $CH(B)$ can be separated into the upper hull and lower hull, where each can be enumerated by a Zonotope, because of the cumulative sum nature.

Some plots showing m=2 condition: the upper and lower hull

And I'm looking into extending the property into $m \geq 3$.

peng yu
  • 1,271
  • I think we need more context to help. It's known that every projection of a zonotope is a zonotope, so if you know one projection that isn't then the original polytope isn't. But it's easy to find examples where a single projection is a zonotope and the original isn't. How many projections do you know, in what dimensions? How independent are they? Please [edit] the question to provide more information. See Theorem 3.3 here: https://www.ams.org/journals/tran/1969-145-00/S0002-9947-1969-0256265-X/S0002-9947-1969-0256265-X.pdf – Ethan Bolker Oct 25 '20 at 18:40
  • Further question to be clarified. Are you looking only at projections that are determined by selecting a subset of the coordinate axes? Note too: every one dimensional projection of every convex set is an interval, hence a zonotope. – Ethan Bolker Oct 25 '20 at 19:03
  • thanks for your interest, I'm updating the description with more context – peng yu Oct 25 '20 at 19:04
  • to summarize, the high-dimensional convex object, doing any linear projection to 2d, the image would be a union of two zonotopes. what can I say about the original object? – peng yu Oct 25 '20 at 19:19
  • This is an interesting question. I may find time to think about it. Quick thoughts. 1. Your $b$ sequence is just an arbitrary sequence of vectors where each coordinate is increasing. Perhaps look at examples on the curve $(x, x^2, x^3, \ldots, x^n)$, start first with $n=3$. – Ethan Bolker Oct 25 '20 at 19:49
  • thank you! and the data from my domain might not possess such a nice structure $(x, x^2, \cdots, x^n)$, but the rest is correct. and just to be sure, in the 2d image, both upper hull and lower hull form two half of a zonotope, since the zonotope is symmetrical.i want to prove even in $m \geq 3$, $CH(B)$ can still be union/intersection of two Zonotope. – peng yu Oct 25 '20 at 19:57
  • And if things can be easier, some type of problems in my domain might have this property $a_i \in \mathbb{N}^m$ – peng yu Oct 25 '20 at 19:59
  • cc @EthanBolker After study the Theorem 3.3, I'm getting more excited about the result. For a high dimensional object $B$, any 2d face can be obtained via linear projection. linear projection commutes with cumsum (using distributivity of Matrix multiplication). And I proved any cumulative sum of 2d points in 1st quadrant can be enumerated by 2 Zonotope. I can almost conclude $B$ can be enumerated by 2 Zonotope. – peng yu Oct 26 '20 at 16:38
  • I'm not sure you can get every two dimensional face as a projection. I don't see how to get any of the rhombic faces of the rhombic dodecahedron that way. Maybe your objects $B$ are special enough for that to be true, but I'm doubtful. If you want to discuss this further you can find my email in my SE profile. – Ethan Bolker Oct 26 '20 at 22:24
  • ah you were right, just sent you an email, and the claim can be relaxed so you can get every 2d face via the linear projection over some subset of vertices. which a subset of the cumulative sum is still cumulative sum :) – peng yu Oct 26 '20 at 23:55

0 Answers0