Skip to main content
Post Undeleted by 2012rcampion
added 7301 characters in body
Source Link
2012rcampion
  • 19k
  • 3
  • 66
  • 98

The firstWe can solve this problem by optimizing the surface area or volume of a tetrahedron in a unit sphere hadand then scaling the solution so the surface area matches the given value.

Let the vectors $\vec x_i,\ i\in\{1\ldots 4\}$ be the four vertices of the tetrahedron. Our first constraint is that the vertices must lie in the (unit) sphere; this can be written as simply:

$$\left\Vert \vec x_i\right\Vert^2\le 1$$

The next constraint is the ratios of the areas of the faces. The areas can be calculated by:

$$ A_i = \frac{1}{2}\left\Vert(\vec x_{i+1}-\vec x_i)\times(\vec x_{i+2}-\vec x_i)\right\Vert $$

(Note the indices wrap around, e.g. $\vec x_5=\vec x_1$.) This is a complex nonlinear constraint but we can convert it to two quadratic constraints by defining a set of auxiliary vectors $\vec c_i,\ i\in\{1\ldots 4\}$:

$$ \vec c_i=(\vec x_{i+1}-\vec x_i)\times(\vec x_{i+2}-\vec x_i) \\ (2A_i)^2 = \left\Vert\vec c_i\right\Vert^2 $$

The defining equation for $\vec c_i$ is quadratic since, when the cross product is expanded, no terms have more than two $x_i$ multiplied together.

The area ratio constraint is then just:

$$ A_i = i A_1 $$

Note that although we have chosen a particular permutation of the faces, due to the symmetries of the tetrahedron any other face permutation is equivalent by permuting the vertices.

The volume can be calculated by:

$$ V = \frac{1}{6}\left|(\vec x_2-\vec x_1)\times(\vec x_3-\vec x_1)\cdot(\vec x_4-\vec x_1)\right| $$

We can rewrite this to use $\vec c_i$, turning it in to a quadratic constraint:

$$ 6V = \vec c_1\cdot(\vec x_4-\vec x_1) $$

Note that the absolute value has disappeared; this is OK since we can convert a negative-signed-volume tetrahedron to a positive one by swapping to vertices.

Writing these constraints in ZIMPL looks like this:

# helper functions
defnumb mod4(i) := ((i - 1) mod 4) + 1;
defnumb mod3(i) := ((i - 1) mod 3) + 1;

# variables
var x[{1..4}*{1..3}] >= -1 <= 1;
var a[{1..4}] >= 0;
var c[{1..4}*{1..3}] >= -infinity <= infinity;
var v >= 0;

# objective; pick one
# maximize total_area: sum <i> in {1..4}: a[i];
maximize volume: v;

# constraints
subto in_sphere: forall <i> in {1..4}: sum <k> in {1..3}: x[i,k]^2 <= 1;
subto cross_prod: forall <i,k> in {1..4}*{1..3}:
    c[i,k] == (x[mod4(i+1),mod3(k+1)]-x[i,mod3(k+1)])*(x[mod4(i+2),mod3(k+2)]-x[i,mod3(k+2)]) - 
              (x[mod4(i+1),mod3(k+2)]-x[i,mod3(k+2)])*(x[mod4(i+2),mod3(k+1)]-x[i,mod3(k+1)]);
subto area: forall <i> in {1..4}: (2*a[i])^2 == sum <k> in {1..3}: c[i,k]^2;
subto area_ratio: forall <i> in {2..4}: a[i] == i * a[1];
subto volume: 6*v == sum <k> in {1..3}: (x[4,k]-x[1,k])*c[1,k];
# constrain orientation to force a unique solution
# the first vertex must lie along the positive x-axis
# the second vertex must lie in the upper x-y plane
subto fix_vertex: x[1,1] >= 0 and x[1,2] == 0 and x[1,3] == 0 and x[2,2] >= 0 and x[2,3] == 0;

I solved this this using SCIP.


The solution for maximal surface area is:

solution status: optimal solution found
objective value:                     3.24759692195701
x#1#1                                               1   (obj:0)
x#2#1                              -0.499648917450054   (obj:0)
x#2#2                               0.866228124582392   (obj:0)
x#3#1                               0.250330301953486   (obj:0)
x#3#2                               0.866138389075211   (obj:0)
x#3#3                            -0.000750267933309599  (obj:0)
x#4#1                              -0.500270727125412   (obj:0)
x#4#2                              -0.865869295355317   (obj:0)
x#4#3                            -0.000453442238582569  (obj:0)
a#1                                 0.324759692195701   (obj:1)
a#2                                 0.649519384391403   (obj:1)
a#3                                 0.974279076587105   (obj:1)
a#4                                  1.29903876878281   (obj:1)
c#1#1                            -0.000648946627302448  (obj:0)
c#1#2                            -0.00112514724035245   (obj:0)
c#1#3                              -0.649518255693092   (obj:0)
c#2#1                            -0.00129950154812839   (obj:0)
c#2#2                            0.000340548156145226   (obj:0)
c#2#3                               -1.29903796871455   (obj:0)
c#3#1                            -0.00104238022931135   (obj:0)
c#3#2                             0.00078613317424887   (obj:0)
c#3#3                                1.94855751247677   (obj:0)
c#4#1                            -0.000391889620475885  (obj:0)
c#4#2                            -0.000680001769731886  (obj:0)
c#4#3                                2.59807741529706   (obj:0)
v                                0.000373725035811096   (obj:0)

Note that $V$ is very small, and the z-coordinates of all the points are zero or nearly zero. The tetrahedron is degenerate (flat), and looks something like this:

We can compute the radius at which the tetrahedron would have an area of 100 cm2 as $r=\sqrt{100/A}$, which is:

5.549055 cm; the associated tetrahedron is degenerate5491 cm


The solution for maximal volume is:

solution status: optimal solution found
objective value:                    0.168616181170499
x#1#1                                               1   (obj:0)
x#2#1                               0.103368738387049   (obj:0)
x#2#2                               0.994643103806537   (obj:0)
x#3#1                               0.446415095883521   (obj:0)
x#3#2                               0.678786929600625   (obj:0)
x#3#3                              -0.433510583267715   (obj:0)
x#4#1                              -0.734126599748252   (obj:0)
x#4#2                               -0.67901272007481   (obj:0)
x#4#3                            -0.000515264692628134  (obj:0)
a#1                                 0.291707753384547   (obj:0)
a#2                                 0.583415506769094   (obj:0)
a#3                                 0.875123260153641   (obj:0)
a#4                                  1.16683101353819   (obj:0)
c#1#1                              -0.431188370044785   (obj:0)
c#1#2                              -0.388698218976949   (obj:0)
c#1#3                             -0.0580016270153901   (obj:0)
c#2#1                              -0.725384940303185   (obj:0)
c#2#2                                0.36324047987551   (obj:0)
c#2#3                                -0.8386700819649   (obj:0)
c#3#1                              -0.294709100335685   (obj:0)
c#3#2                               0.751477471806906   (obj:0)
c#3#3                                1.55299391553877   (obj:0)
c#4#1                            -0.000512554591328825  (obj:0)
c#4#2                            -0.000462485871227904  (obj:0)
c#4#3                                2.33366155968202   (obj:0)
v                                   0.168616181170499   (obj:1)

The tetrahedron looks something like:

(flat):

The second sphere hadhas a radius of:

6.029263 cm; the associated tetrahedron has a volume of about 355.011 cm3:
8550 cm

Solutions found using SCIP; codeAnd the volume of the here.(scaled) tetrahedron is

33.844 cm3

The first sphere had a radius of:

5.549055 cm; the associated tetrahedron is degenerate (flat):

The second sphere had a radius of:

6.029263 cm; the associated tetrahedron has a volume of about 35.011 cm3:

Solutions found using SCIP; code here.

We can solve this problem by optimizing the surface area or volume of a tetrahedron in a unit sphere and then scaling the solution so the surface area matches the given value.

Let the vectors $\vec x_i,\ i\in\{1\ldots 4\}$ be the four vertices of the tetrahedron. Our first constraint is that the vertices must lie in the (unit) sphere; this can be written as simply:

$$\left\Vert \vec x_i\right\Vert^2\le 1$$

The next constraint is the ratios of the areas of the faces. The areas can be calculated by:

$$ A_i = \frac{1}{2}\left\Vert(\vec x_{i+1}-\vec x_i)\times(\vec x_{i+2}-\vec x_i)\right\Vert $$

(Note the indices wrap around, e.g. $\vec x_5=\vec x_1$.) This is a complex nonlinear constraint but we can convert it to two quadratic constraints by defining a set of auxiliary vectors $\vec c_i,\ i\in\{1\ldots 4\}$:

$$ \vec c_i=(\vec x_{i+1}-\vec x_i)\times(\vec x_{i+2}-\vec x_i) \\ (2A_i)^2 = \left\Vert\vec c_i\right\Vert^2 $$

The defining equation for $\vec c_i$ is quadratic since, when the cross product is expanded, no terms have more than two $x_i$ multiplied together.

The area ratio constraint is then just:

$$ A_i = i A_1 $$

Note that although we have chosen a particular permutation of the faces, due to the symmetries of the tetrahedron any other face permutation is equivalent by permuting the vertices.

The volume can be calculated by:

$$ V = \frac{1}{6}\left|(\vec x_2-\vec x_1)\times(\vec x_3-\vec x_1)\cdot(\vec x_4-\vec x_1)\right| $$

We can rewrite this to use $\vec c_i$, turning it in to a quadratic constraint:

$$ 6V = \vec c_1\cdot(\vec x_4-\vec x_1) $$

Note that the absolute value has disappeared; this is OK since we can convert a negative-signed-volume tetrahedron to a positive one by swapping to vertices.

Writing these constraints in ZIMPL looks like this:

# helper functions
defnumb mod4(i) := ((i - 1) mod 4) + 1;
defnumb mod3(i) := ((i - 1) mod 3) + 1;

# variables
var x[{1..4}*{1..3}] >= -1 <= 1;
var a[{1..4}] >= 0;
var c[{1..4}*{1..3}] >= -infinity <= infinity;
var v >= 0;

# objective; pick one
# maximize total_area: sum <i> in {1..4}: a[i];
maximize volume: v;

# constraints
subto in_sphere: forall <i> in {1..4}: sum <k> in {1..3}: x[i,k]^2 <= 1;
subto cross_prod: forall <i,k> in {1..4}*{1..3}:
    c[i,k] == (x[mod4(i+1),mod3(k+1)]-x[i,mod3(k+1)])*(x[mod4(i+2),mod3(k+2)]-x[i,mod3(k+2)]) - 
              (x[mod4(i+1),mod3(k+2)]-x[i,mod3(k+2)])*(x[mod4(i+2),mod3(k+1)]-x[i,mod3(k+1)]);
subto area: forall <i> in {1..4}: (2*a[i])^2 == sum <k> in {1..3}: c[i,k]^2;
subto area_ratio: forall <i> in {2..4}: a[i] == i * a[1];
subto volume: 6*v == sum <k> in {1..3}: (x[4,k]-x[1,k])*c[1,k];
# constrain orientation to force a unique solution
# the first vertex must lie along the positive x-axis
# the second vertex must lie in the upper x-y plane
subto fix_vertex: x[1,1] >= 0 and x[1,2] == 0 and x[1,3] == 0 and x[2,2] >= 0 and x[2,3] == 0;

I solved this this using SCIP.


The solution for maximal surface area is:

solution status: optimal solution found
objective value:                     3.24759692195701
x#1#1                                               1   (obj:0)
x#2#1                              -0.499648917450054   (obj:0)
x#2#2                               0.866228124582392   (obj:0)
x#3#1                               0.250330301953486   (obj:0)
x#3#2                               0.866138389075211   (obj:0)
x#3#3                            -0.000750267933309599  (obj:0)
x#4#1                              -0.500270727125412   (obj:0)
x#4#2                              -0.865869295355317   (obj:0)
x#4#3                            -0.000453442238582569  (obj:0)
a#1                                 0.324759692195701   (obj:1)
a#2                                 0.649519384391403   (obj:1)
a#3                                 0.974279076587105   (obj:1)
a#4                                  1.29903876878281   (obj:1)
c#1#1                            -0.000648946627302448  (obj:0)
c#1#2                            -0.00112514724035245   (obj:0)
c#1#3                              -0.649518255693092   (obj:0)
c#2#1                            -0.00129950154812839   (obj:0)
c#2#2                            0.000340548156145226   (obj:0)
c#2#3                               -1.29903796871455   (obj:0)
c#3#1                            -0.00104238022931135   (obj:0)
c#3#2                             0.00078613317424887   (obj:0)
c#3#3                                1.94855751247677   (obj:0)
c#4#1                            -0.000391889620475885  (obj:0)
c#4#2                            -0.000680001769731886  (obj:0)
c#4#3                                2.59807741529706   (obj:0)
v                                0.000373725035811096   (obj:0)

Note that $V$ is very small, and the z-coordinates of all the points are zero or nearly zero. The tetrahedron is degenerate (flat), and looks something like this:

We can compute the radius at which the tetrahedron would have an area of 100 cm2 as $r=\sqrt{100/A}$, which is:

5.5491 cm


The solution for maximal volume is:

solution status: optimal solution found
objective value:                    0.168616181170499
x#1#1                                               1   (obj:0)
x#2#1                               0.103368738387049   (obj:0)
x#2#2                               0.994643103806537   (obj:0)
x#3#1                               0.446415095883521   (obj:0)
x#3#2                               0.678786929600625   (obj:0)
x#3#3                              -0.433510583267715   (obj:0)
x#4#1                              -0.734126599748252   (obj:0)
x#4#2                               -0.67901272007481   (obj:0)
x#4#3                            -0.000515264692628134  (obj:0)
a#1                                 0.291707753384547   (obj:0)
a#2                                 0.583415506769094   (obj:0)
a#3                                 0.875123260153641   (obj:0)
a#4                                  1.16683101353819   (obj:0)
c#1#1                              -0.431188370044785   (obj:0)
c#1#2                              -0.388698218976949   (obj:0)
c#1#3                             -0.0580016270153901   (obj:0)
c#2#1                              -0.725384940303185   (obj:0)
c#2#2                                0.36324047987551   (obj:0)
c#2#3                                -0.8386700819649   (obj:0)
c#3#1                              -0.294709100335685   (obj:0)
c#3#2                               0.751477471806906   (obj:0)
c#3#3                                1.55299391553877   (obj:0)
c#4#1                            -0.000512554591328825  (obj:0)
c#4#2                            -0.000462485871227904  (obj:0)
c#4#3                                2.33366155968202   (obj:0)
v                                   0.168616181170499   (obj:1)

The tetrahedron looks something like:

The sphere has a radius of:

5.8550 cm

And the volume of the (scaled) tetrahedron is

33.844 cm3

Post Deleted by 2012rcampion
Source Link
2012rcampion
  • 19k
  • 3
  • 66
  • 98

The first sphere had a radius of:

5.549055 cm; the associated tetrahedron is degenerate (flat):

The second sphere had a radius of:

6.029263 cm; the associated tetrahedron has a volume of about 35.011 cm3:

Solutions found using SCIP; code here.