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}$.

Improve this question
$\endgroup$
8
  • $\begingroup$ All cells contain the origin $(0,\dots,0)$ so the diameter is at least $1$. Or did I missunderstand something? $\endgroup$
    – user35593
    Commented Dec 17, 2015 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
    Commented Dec 17, 2015 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
    Commented Dec 17, 2015 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
    Commented Dec 17, 2015 at 21:04
  • $\begingroup$ @user35593: I only intended for the simplex to contain points whose coordinates sum to exactly 1. $\endgroup$
    – User123321
    Commented Dec 17, 2015 at 21:12

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ the $\approx\frac{1}{2}$ really is $\frac{\sqrt{6}}{5}$, I guess $\endgroup$
    – Moritz Firsching
    Commented Dec 18, 2015 at 16:43
  • $\begingroup$ @MoritzFirsching: Thanks. $0.4899$. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 18, 2015 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
    Commented Dec 21, 2015 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
    Commented Dec 21, 2015 at 16:00

You must log in to answer this question.

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