Simplex splitting using center of gravity

[vlnikolic]

hello to all


INTRODUCTION:

i have created application that splits triangles (2d simplex) and tetrahedrons (3d simplex) to

1 triangle -> 3 quadrilaterals
1 tetrahedron -> 4 bricks (8 nodal elements)

my application uses element center of gravity in both cases. and than splits.

for triangle new nodes are in
cogs of edges
cog of triangle

for tetrahedron new nodes are in
cogs of edges
cogs of triangles
cog of tetrahedron

as shown in these pictures:
http://img534.imageshack.us/img534/6105/triangleg.jpg
http://img225.imageshack.us/img225/112/tetrahedron.jpg


QUESTION:

i would like to have mathematical proof that all the new elements

case 1 - quadrilaterals
case 2 - bricks

are convex

when elements are splited in this way.


thank you for your interest very much

 

[quasar987]

What you've done here is only draw a picture. You haven't defined mathematically your construction, so proving anything about it doesn't make sense. Here is a way to define your construction mathematically. You start the triangle. Label the midpoints of each edge P1, P2, P3 and the vertices V1, V2, V3. Also call C the center of gravity of the triangle. Now define the 3 quadrilaterals Q1, Q2, Q3 like so:

Q1:= convex hull of the points V1, P1, P2, C
Q2:= convex hull of the points V2, P1, P3, C
Q2:= convex hull of the points V3, P2, P3, C

http://en.wikipedia.org/wiki/Convex_hull

Now, to prove that your quadrilaterals are convex boils down to proving that the convex hull of a set of points is a convex set, which is easy.

 

[Office_Shredder]

No, his construction does not take convex hulls directly. For example if the center of gravity was somewhere wacky in the triangle you could get something like this

http://img709.imageshack.us/f/cogoff.jpg/

For the triangle case all you have to do is prove that the center of gravity does not lie in the triangle formed by a vertex and the two center of gravities lying on the edges touching the vertex
For the partitioning of the tetrahedron to prove convexity (once you have convexity for the triangle) you just need that the center of gravity of the tetrahedron does not lie inside the smaller tetrahedron formed by taking the plane passing through three center of gravities and the vertex that lies inside the three faces containing those center of gravities

Once you have such a proof you could imagine immediately extending it to higher dimensions to partition any simplex

EDIT TO ADD: If you know that every point in a triangle can be written uniquely as a convex sum of the vertices this turns out the be fairly simple

 

[quasar987]

Err, I think the OP is only interested in the case that he drew because as your example illustrates, the quadrilaterals in the case of a general mass distribution need not be convex.

Am I wrong?

 

[Office_Shredder]

Obviously my picture isn't an example of what the OP wanted, because there is no example where the bodies you get will be concave. The point is that you aren't just taking the convex hull of four points

 

[vlnikolic]

hello to all
and thank you very much for your interest and repl.


i have posted the same question on other places - thus it is a bit more clear to me what and how i should create the proof

right now i am not in place where i can write more but i would like to add 2 images that i created yesterday just in case they can help

http://img831.imageshack.us/img831/8260/trianglenum.jpg
http://img14.imageshack.us/img14/6287/tetrahedronnum.jpg

cheers

 

[quasar987]

Obviously my picture isn't an example of what the OP wanted, because there is no example where the bodies you get will be concave. The point is that you aren't just taking the convex hull of four points

Why is my definition of the bodies the OP is interested in in terms of convex hull wrong then?! I'm really confused about the point you're trying to make.

 

[Office_Shredder]

Why is my definition of the bodies the OP is interested in in terms of convex hull wrong then?! I'm really confused about the point you're trying to make.

Because he's asking for the quadrilateral defined by four points, not the convex hull defined by them. The convex hull might be a triangle, and the quadrilateral might not be convex (in this case it is, but not because it's defined as a convex hull). By assuming that the quadrilateral is defined as a convex hull of the potential vertices you've already assumed that it's convex before you've proven it.

For example, to prove this for the triangle: the center of mass is at the barycenter \frac{1}{3}(a+b+c) where a,b and c are the vertices of the triangle. Suppose that this lies inside one of the triangles formed by two midpoints of edges and a vertex; say inside the triangle \frac{1}{2}(a+b), \frac{1}{2}(a+c) and a (which would mean that the quadrilateral formed by these three points and the center of gravity of the triangle is not convex). Then the center of the triangle can be written as a convex sum of the three other vertices:

\frac{1}{3}(a+b+c)=\alpha_1 a + \alpha_2 \frac{1}{2}(a+b) + \alpha_3 \frac{1}{2} (a+c) = \frac{1}{2} (\alpha_1 + \alpha_2 + \alpha_3) a + \frac{1}{2}(\alpha_1 a + \alpha_2 b + \alpha_3 c) = \frac{1}{2}a + \frac{1}{2}(\alpha_1 a + \alpha_2 b + \alpha_3 c) using the fact that the sum of the alpha coefficients is 1. Each point in the triangle can be written uniquely as a convex combination of a, b and c, but the first step has a 1/3 coefficient in front of the a, and the end step has a coefficient greater than or equal to 1/2 which is a contradiction. Hence the center of gravity does not lie inside of the triangle formed by a vertex and the two adjacent midpoints, and the four quadrilaterals formed are all convex

 

[quasar987]

Because he's asking for the quadrilateral defined by four points, not the convex hull defined by them. The convex hull might be a triangle, and the quadrilateral might not be convex

Ok, I think I understand what's in your mind. You are saying that if the quadrilaterals are defined by drawing straight lines from the midpoints of the edges to the center of mass, then for some distribution of mass, this need not coincide with the convex hull of the 4 vertices of the quadrilateral.

I think this is a big "if" because the OP never actually said how he defined the quadrilaterals in his programs code. He just said "I used the center of mass, and then split" (whatever that means). But he also drew a picture illustrating the quadrilaterals he is talking about.

The whole point of my post is that if these are the quadrilaterals he is are interested in then he might as well define them as

Q1:= convex hull of the points V1, P1, P2, C
Q2:= convex hull of the points V2, P1, P3, C
Q2:= convex hull of the points V3, P2, P3, C

in which case their convexity is easily proven. (where obviously, here, C is the center of mass for a uniform mass density, otherwise we don't get the quadrilaterals the OP is interested in! )

 

[adriank]

Note that the center of mass is preserved by affine transformations, and so is convexity. Thus, once you've proven it for one triangle or tetrahedron (or simplex in general), you have proven it for all of them (because any two n-simplexes are affinely equivalent).

 

[vlnikolic]

hello again to all
i would like to thank you very much for your time and interest


i would like to add one picture and comment concerning new nodes and elements in tetrahedron case. just to be more defined.


TETRAHEDRON CASE

part I: INITIAL NODES

initial tetrahedron has 4 nodes: 1, 2, 3 and 4

let we say that the initial tetrahedron is build of several elements:
1) edges (I-D elements)
2) faces (II-D elements) - triangles
3) one tetrahedron (III-D element)

new nodes are positioned in center of gravity-ies (cogs) of elements that the initial tetrahedron is build of.

new nodes we can classify like this:

I-D cogs: 5, 6, 7, 8, 9, 10
II-D cogs: 11, 12, 13, 14
III-D cog: 15

at this point we do have new 15-node tetrahedron.


part I: NEW ELEMENTS

new elements are 8-nodal bricks. they are created like this:
http://img826.imageshack.us/img826/9230/g4634.jpg

thus we have 4 bricks:

1) 8, 11, 15, 13, 1, 5, 14, 7
2) 9, 12, 15, 11, 2, 6, 14, 15
3) 10, 13, 15, 12, 3, 7, 14, 6
4) 10, 13, 15, 12, 4, 8, 11, 9

http://img826.imageshack.us/img826/9230/g4634.jpg

i am sorry - i was not well defined with question @ start