Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  joriki Apr 28 '11 at 21:03
    
Thanks @joriki. I've updated the question. I really meant, does this winding/rotation of the vertices give us a negative or positive determinant? –  Will Bradley Apr 28 '11 at 21:28
    
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. –  J. M. Apr 28 '11 at 21:29
    
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.) –  Will Bradley Apr 28 '11 at 21:35
2  
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. –  Robert Israel Apr 28 '11 at 23:20

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
Thanks @user9325, this is exactly what I was unable to see. –  Will Bradley Apr 29 '11 at 18:26

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

share|improve this answer
    
Also, for permuting the vertices, you will change the orientation if it is an odd permutation. –  yasmar Apr 29 '11 at 5:52
    
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. –  Will Bradley Apr 29 '11 at 18:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.