This nice little paper should be of interest for this thread: https://www.ems-ph.org/journals/show_pdf.php?issn=0013-6018&vol=64&iss=4&ran... On Thu, Jan 21, 2016 at 7:37 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Just to put all this in context: a vector of 6 (ordered) distances corresponds to a proper Euclidean tetrahedron just when it admits some flag (vertex in edge in face in solid) for which every squared content (computed via C-M) is positive.
WFL
On 1/21/16, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I see it's getting on for ten years since I last explained this --- evidently long enough for some to have forgotten all about it, as well as (perhaps) a few newcomers to arrive who ought to be introduced to it. So with that apologia, verbatim:
<<
... it might just be useful to quote the exact algebraic result here, which is from a little-known corner known as "Distance Geometry" --- refer to the book by Leon Blumenthal (if you can find it).
Suppose we have n+1 notional "points" P_i , for which we know only the squared distances U_{ij} = |P_i - P_j|^2 . If they are embeddable in Euclidean n-space, then the squared content of the simplex is given by the Cayley- Menger determinant
D_{n+2} = | 0 -1 -1 ... -1 | | -1 -U_{00} -U_{01} ... -U_{0n} | | . . | - | . . | / 2^n (n!)^2 | . . | | -1 -U_{n0} -U_{n1} ... -U_{nn} |
[view w/o proportional spacing!]
Then for an arbitrary set of points to be properly embeddable, it is necessary and sufficient that there exists some numbering of the points so that the n numbers D_3, ..., D_{n+2} are all positive.
Notice that the improper case (when the n+1 points are possibly embeddable in fewer than n dimensions) is NOT the limit of the proper case: there exist unembeddable configurations for which the D_k of some numberings are non-negative. It is however sufficient that ALL possible numberings give nonnegative determinants.
For m >= n+3 points, they are embeddable just when every subset of n+1 is embeddable. However, the case m = n+2 is peculiar: there exist "pseudo- Euclidean" sets of n+2 points which are not embeddable, even tho' every subset is (of course, it follows by the above that D_{n+3} < 0 for such a configuration).
Unless anyone's interested in this stuff, I shan't take up bandwidth with any more details. However, there are two unsolved problems in this area that interest me. The first concerns the topology of the (essentially cubic) variety in 4-D projective space corresponding to "tetrahedra" of zero volume: for example, is it connected? what are its singularites? etc. (Incidentally, this polynomial --- the squared volume of the tetrahedron in terms of its edge-lengths --- frequently gets rediscovered, at great length, by people like me. Including me.)
The second concerns pseudo-Euclidean sets: for example, in n=2 dimensions these are constructed from a triangle P,Q,R say, together with an arbitrary point S in the plane and its "isogonal conjugate" T (see e.g. H.S.M.Coxeter's Introduction to Geometry). Let the squared edges of the triangle be U,V,W , and the squared distances of S from P,Q,R be X,Y,Z ; then the squared isogonal radius is a rational function of U,V,W,X,Y,Z . But the power of my symbolic algebra package is insufficient to compute it!
Fred Lunnon
On 1/21/16, Henry Baker <hbaker1@pipeline.com> wrote:
Off the top of my head, I don't have answers to any of Rich's questions.
However, the computer graphics people have done a lot of work on similar issues having to do with things like triangles intersecting triangles (in 3D !) and tetrahedra intersecting tetrahedra.
Amazingly, the best algorithms aren't as clever as one might expect; they look a lot more like multiple-precision brute force.
I don't know whether there are provable lower bounds on any of these algorithms, so there may still be room for improvement.
(A lower bound might show that computing some feature of a complex polyhedron might solve some other known problem -- e.g., satisfiability or colorability.)
I'm also interested in whether there are "modular analogs" to some of these questions in a modular space. I.e., a classical sort of algorithm, but computed modulo some integer or some polynomial.
At 04:52 PM 1/20/2016, rcs@xmission.com wrote:
When does a set of edge lengths make a triangle?
Assume that the lengths are non-negative. Then we need the triangle inequality, A+B <= C. We can either check all three permutations, or require the lengths are sorted, with C maximal. When the inequality is an equality, then A+B-C is zero, and Hero(n?)'s Formula for the area, S = 1/4 * sqrt((A+B+C)(A+B-C)(A-B+C)(-A+B+C)) is 0. Moreover, if A,B,C >=0, at most one of the factors in the sqrt can be negative, so looking at the sign of the radicand signals the reality of the triangle.
Puzzle: Same problem, in 3D. When do six edges make a real tetrahedron?
Assume the base triangle edges are A,B,C, with opposite edges D,E,F. The four faces must be real triangles; moreover the area of the largest face must be no greater than the sum of the areas of the other three faces. This constraint is obviously true for a real tetrahedron. Necessity follows from the example A=B=C=7, D=E=F=4, where the area of the base ABC exceeds the sum of areas of the three skinny 744 triangles. (In a 777 triangle, the distance from the center to a vertex is 7/sqrt3 = 4.04...)
Another possible geometry failure: Build the tetrahedron as a planar quadrilateral, with the diagonals TBD. If we choose one diagonal, its length is restricted (both min & max) by the triangle inequality. Now imagine the quadrilateral as two triangles with the (first) diagonal as a hinge: The second diagonal must be long enough to connect the two remaining vertices, but not too long. I can make a too-long example with the quadrilateral (a rhombus) having sides 2,2,2,2. If arranged as a square, the diagonals would be 2sqrt2 = 2.828...; requiring each diagonal to be 3 gives an impossible tetrahedron which satisfies the various triangle inequalities, and the sum-of- areas constraints.
One puzzle is to find something analogous to the sum-of-areas constraint that captures this second-diagonal-not-too-long restriction.
I think that the second-diagonal-too-short case is covered by the sum-of-areas constraint: If SOA is true, then 2nd-diag-too-short can't happen.
Another puzzle is to find something analogous to Hero(n?)'s formula, for the volume. One might hope that the volume could be expressed in terms of the areas of the four faces, but I think this is false. It is true in the case of a "right-tetrahedron", where one vertex is the corner of three right triangles: The volume is the (sqrt2)/3 of the square root of the product of the areas of the three right triangles. The area of the "hypotenuse" face is fixed in this case, by a 3D version of Pythagoras: square-of-hyp-area = sum of squares of other three face areas.
There's a volume formula in terms of the six edges, as the square-root of a sixth-degree polynomial. I don't know of any formula which uses the area- excesses as factors, analogous to the appearance of the edge-excesses (i.e. A+B-C &c) in Hero(n?)'s area formula.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun