2
$\begingroup$

Assertion: With any simplex $P$ with vertices $V_{0..N+1} \subset R^N$, it is possible to compute the sign of the oriented volume using the expression $det(V_1-V_0, V_2-V_0, ..., V_{N-1}-V_0, V_{N}-V_0)$, where the vector differences are represented as a list of column vectors.

Further, it is possible to permute the indices of the vertices, so as to "rotate" them $k$ times so that $V'_i := V_{((i + k) \mod (N+1))}$, and the determinant stays the same.

However, this does not seem to hold with simplices in $R^1$ (where the simplex is a line segment) and it prevents some simple tests from working in the general case. What am I leaving out, or how is my assertion incorrect? My gut is telling me there's something special about the first dimension that's missing from my rotation operation.

Can anyone explain this special case?

$\endgroup$
9
  • $\begingroup$ I get only a handful of Google hits for "boolean convexity", and none of them seem to define the term. That's a good sign you should probably include a definition. $\endgroup$
    – joriki
    Apr 28, 2011 at 21:03
  • $\begingroup$ Thanks @joriki. I've updated the question. I really meant, does this winding/rotation of the vertices give us a negative or positive determinant? $\endgroup$ Apr 28, 2011 at 21:28
  • $\begingroup$ In $R^1$ your simplex is a triangle, 'no? Remember that swapping rows/columns of a determinant changes its sign... for the example of a triangle, you want to order your vertices in anticlockwise fashion. $\endgroup$ Apr 28, 2011 at 21:29
  • $\begingroup$ Thanks J.M.. However, in $R^1$ the simplex is a segment. In $R^2$ (the simplex is a triangle), rotation of the indices always causes two column swaps, which cancel each other out (in terms of negation of the determinant.) $\endgroup$ Apr 28, 2011 at 21:35
  • 2
    $\begingroup$ As far as I know, every simplex is convex. What your determinant tests has nothing to do with convexity, but rather with the arrangement of the list of vertices of the simplex. $\endgroup$ Apr 28, 2011 at 23:20

2 Answers 2

4
$\begingroup$

I think one of the main problems is the language you are using. If the $V_i$ are the vertices of an $N$-simplex in $\mathbb{R}^N$, then \begin{equation} \det (V_1-V_0,\ldots, V_N-V_0) \end{equation} is equal to $N!$ times the oriented volume of the simplex. This is discussed on the Wikipedia page. You are using "convex" when you mean positively oriented I think. (I think you also say "rotate the vertices" when you mean permute the vertices.)

I do not see the problem you are having in $\mathbb{R}^1$, but that may be because you have edited the question in response to comments without realizing that it fixed the problem. A 1-simplex has two vertices $V_0$, and $V_1$. In this case $\det(V_1-V_0) = V_1-V_0$ since it is a $1\times 1$ matrix. It is the length of your segment, and the orientation is positive if $V_1 \gt V_0$.

$\endgroup$
2
  • $\begingroup$ Also, for permuting the vertices, you will change the orientation if it is an odd permutation. $\endgroup$
    – yasmar
    Apr 29, 2011 at 5:52
  • $\begingroup$ Thanks! This answer is on the right track, and I will correct the question so that the language is more obvious. I suppose I wasn't really asking about convexity, as you point out, I did in fact mean "positively oriented." The trick that @user9325 pointed out was the difference between "rotation" permutations in odd or even dimensions. $\endgroup$ Apr 29, 2011 at 18:30
3
$\begingroup$

It is simply wrong that a "rotation" of the vertices does not change the orientation (i.e. sign of the determinant).

A "rotation" is a cyclic permutation which is odd if and only if the number of permuted elements is even. So, in the corrected version, the rotation will preserve orientation for even $N$ and change orientation for odd $N$.

$\endgroup$
1
  • $\begingroup$ Thanks @user9325, this is exactly what I was unable to see. $\endgroup$ Apr 29, 2011 at 18:26

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.