2
$\begingroup$

Consider a standard simplex with points $(p_1, \dots, p_n)$, $p_i \ge 0$, and $\sum_i p_i = 1$. Fix a set $\{q_k\}_{k=1}^K$ with $0\leq q_k \leq \infty$ and $i,j\in\{1, \dots, n\}$. Partition it via the hyperplanes characterized by $p_i = q_k p_j$ into "cells" so that each cell is the intersection of one of the half-spaces generated by each hyperplane. (For concreteness, for the case of the 2-simplex, I have in mind a triangle. There are $K$ lines emanating from each vertex, intersecting the opposite edge of the triangle. These lines subdivide the triangle into a number of disjoint regions, which I am calling cells. Note that there are $K{n \choose 2}$ hyperplanes, so each cell is an intersection of $K{n\choose 2}$ half-spaces.)

Suppose that the $\{q_k\}$ are such that the hyperplanes are "evenly spaced." By evenly spaced, I mean that $\{q_k\}$ is such that $q_k / (1+q_k) = k / (K+1)$. (In the 2-simplex, this corresponds to the lines dividing the opposite edge into equally spaced segments.)

What is the maximal diameter of one of the cells of this partition, as a function of $K$ and $n$? Is there a way to compute a (reasonable) upper bound for this diameter? (An answer even for the 2-simplex would be very helpful!) Suppose for concreteness that we are looking at the Euclidean metric induced from the ambient space, with all edges having side length $\sqrt{2}$.

$\endgroup$
  • $\begingroup$ All cells contain the origin $(0,\dots,0)$ so the diameter is at least $1$. Or did I missunderstand something? $\endgroup$ – user35593 Dec 17 '15 at 17:51
  • $\begingroup$ So there are $K \binom{n}{2}$ hyperplanes? For a triangle, $3 \binom{n}{2} $ lines forming the partition? $\endgroup$ – Joseph O'Rourke Dec 17 '15 at 17:54
  • 3
    $\begingroup$ Possible duplicate of What is the minimal number of lines needed to partition a simplex into cells of diameter at most $\epsilon$? Since you are the same OP, why did you not even refer to that question of yours? The only difference is that now you ask for evenly space intersection points on the opposite edge. $\endgroup$ – Sebastian Goette Dec 17 '15 at 18:37
  • $\begingroup$ Sorry, I hadn't realized it was forum convention to link to previous questions. As you mentioned, the previous question asked for the optimal partitioning on the simplex. This one asks for a bound on the cell diameter for a particular partitioning. $\endgroup$ – User123321 Dec 17 '15 at 21:04
  • $\begingroup$ @user35593: I only intended for the simplex to contain points whose coordinates sum to exactly 1. $\endgroup$ – User123321 Dec 17 '15 at 21:12
3
$\begingroup$

This is not an answer, just an illustration of what seems to be your question. For the equilateral triangle of side length $\sqrt{2}$, and $K=3$, the largest diameter cell is incident to a corner. It has diameter $\approx \frac{1}{2}$. (I didn't compute it exactly.)


      TriPartition
      Equilateral triangle, $K=3$.
For a regular simplex, a guess would be that a maximal diameter cell is again incident to a corner, and with a facet determined by the $\lceil K/2 \rceil$-th hyperplane, i.e., the cell lies on the hyperplane bisector.

$\endgroup$
  • 1
    $\begingroup$ the $\approx\frac{1}{2}$ really is $\frac{\sqrt{6}}{5}$, I guess $\endgroup$ – Moritz Firsching Dec 18 '15 at 16:43
  • $\begingroup$ @MoritzFirsching: Thanks. $0.4899$. $\endgroup$ – Joseph O'Rourke Dec 18 '15 at 18:53
  • $\begingroup$ @JosephO'Rourke. Thanks a lot for the diagram and suggestion. I agree (by drawing pictures) that this seems to be the case for $n=3$ and larger $K$ as well. (And, the exact length of this segment can of course be computed analytically for all $K$.) Do you have any further justification for this conjecture? Also, would it help to find (reasonable) upper bounds for this diameter, without nailing it exactly? I edited the question to reflect this, but I am worried that asking for suggestions for upper bounds is too open-ended. $\endgroup$ – User123321 Dec 21 '15 at 6:04
  • $\begingroup$ @User123321: The intuition is that, between two adjacent hyperplanes, the longest cuts are those furthest from the hyperplane's common vertex, because the hyperplanes spread. So perhaps you could prove monotonicity as one hyperplane cuts through the fan of hyperplanes emanating from one vertex. $\endgroup$ – Joseph O'Rourke Dec 21 '15 at 16:00

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.