5
$\begingroup$

The problem setup is simple: Given a $d$-simplex $\Delta_d:=\{(x_1,\cdots,x_d):x_i\geq 0,\sum_i x_i\leq 1\}$, can we construct a finite sequence of parallelotope $A_i$ so that $\Delta_d=\cup_{i=1}^N A_i$, where $N$ may depend optimally on $d$ in the sense any sequence of such covers must have cardinality lower bounded by $N$ up to a universal constant.

The problem in dimension $d=1,2$ is straightforward. However even in $d=3$, it is not clear to me if there is such a construction.

My main motivation for such a result is trying to reduce certain problem on simplex to parallelotope, which is easier to handle.

Any comment shall be greatly appreciated.

$\endgroup$
1
$\begingroup$

Edit 1: Indeed, my previous suggestion was not good. As it has been pointed out to me by Dongryul Kim, the parallelotopes should be finitely many. I have overlooked that. Maybe this could work?

Construction 1:

In the case of a triangle $ABC$ we define a parallelogram at vertex $A$ to be a parallelogram constructed as follows: pick a point $Q$ on $BC$ and draw the two lines parallel to $AB$ and $AC$.

Induction: Take a $d-1$ face $f$ of the $d$-simplex and the opposite vertex $v$ (the one vertex which is not on $f$). Take a vertex $w$ of $f$. Look at the edge $vw$. Take a point $p$ on $vw$ and draw the hyper-plane $L$ through $p$ parallel to $f$. $L$ intersects the simplex in a $d-1$ simplex $f'$ similar to $f$ (actually homothetic from vertex $v$). Draw the parallelotope on $f'$ with vertex $p$ (see first step above or inductive step). Translate it to $f$ by the vector $\overrightarrow{pw}$ to obtain the desired $d$-dimensional parallelotope at vertex $w$.

Construction 2:

A parallelogram sitting on the edge $AB$ of triangle $ABC$ is a parallelogram defined as follows: Take midpoint $M$ on $AB$ and pick a point $Q$ on $CM$. Draw line parallel to $AB$ to form a segment parallel to $AB$ and then translate it down to $AB$ with vector $\overrightarrow{QM}$.

Induction: Pick a face $d-1$ dimensional face $f$ of the $d$-simplex and let $v$ be the vertex opposite to it (like before). Let $M$ be the barycenter of $f$ and choose a point $p$ on $vM$. Draw a $d-1$ hyperplane $L$ through $p$ parallel to $f$. $L$ intersects the $d$-simplex in a $d-1$ simplex $f'$ homothetic to $f$ (and parallel). choose a $d-2$ face $f''$ of $f'$ and draw the parallelotope sitting on $f''$ by induction. Now, translate it via the vector $\overrightarrow{pM}$ to $f$. Thus, one obtains a $d$-parallelotope sitting on $f$.

Seem like using these two procedures one can cover the simplex with finitely many parallelotopes for large enough $N$, by various combinations of face $f$, vertex $w \in f$ and point $p \in vw$ choices. Like various midpoints / barycenters for instance. Maybe only the first procedure is enough, but the second may lower the number of parallelotopes. I guess it depends on the problem. Do we need an estimate on the number $N$ in terms of $d$?

$\endgroup$
2
  • 1
    $\begingroup$ I think what the OP wanted was a finite set of parallelepipeds. $\endgroup$ – Dongryul Kim Aug 3 '15 at 9:58
  • $\begingroup$ Thanks for the answer. I may have not clearly expressed the real issue: The existence for finite cover is not so hard, what I am concerned with the an explicit construction that leads to the minimum covering number (up to correct order scaling with $d$). This seems much more involved $\endgroup$ – Roy Han Aug 4 '15 at 21:20
1
$\begingroup$

EDIT: This is an answer to the previous version of the question, asking for an existence of a finite number of required polytopes.

The answer is obviously yes by a compactness argument:

Consider $\Delta^d$ as a (compact) topological space. For any $x \in \Delta^d$, there is a parallelotope $P_x$ containing $x$ in $P_x'$ where $P_x'$ is the interior of $P_x$ in $\Delta^d$. (Note that the interior is indeed taken in $\Delta^d$ and not in $\mathbb{R}^d$.)

Thus $P'_x$ form an open cover of $\Delta^d$ and there is a finite subcover $\{P'_{x_i}\}$. The required set of parallelotopes is then $\{P_{x_i}\}$.

This reasoining does not say what are the required parallelotopes. But I believe that it is actually not very hard to find the required finite set (not too big) of them by choosing $x_i$ and $P_{x_i}$ suitably.

$\endgroup$
5
  • $\begingroup$ Yes, compactness argument will give a very easy proof. I think I may have not expressed in a clearer way of my concern: I'm concerned with the question that, how many parallelotopes do we need at least, to cover the simplex, i.e. asking for the minimum covering number, or getting an estimate of such number that scales with dimension $d$ with the correct order. $\endgroup$ – Roy Han Aug 4 '15 at 21:18
  • $\begingroup$ I realized this is a little problematic in the sense that you'll need open covers, which simple is not true when $x_i$ is at the boundary of $\Delta^d$. $\endgroup$ – Roy Han Aug 5 '15 at 20:50
  • $\begingroup$ @RoyHan That is why I use the sets $P'_x$ open in the simplex (and not $\mathbb{R}^d$). It is written there. $\endgroup$ – Martin Tancer Aug 5 '15 at 21:09
  • $\begingroup$ How do you do these for boundary points? Will $P'_{x_i}$ exclude $x_i$? $\endgroup$ – Roy Han Aug 5 '15 at 21:20
  • $\begingroup$ No. Imagine a triangle, a vertex $x$ of this triangle and $P_x$ to be a parallelogram with the faces (segments) parallel with the two edges of the triangle incident to $x$. Then $P'_x$ contains $x$ as well as almost completely the two segments of $P_x$ incident of $x$. (On the other hand, it does not contain the remaining two segments of $P_x$.) $\endgroup$ – Martin Tancer Aug 5 '15 at 21:31

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.