5
$\begingroup$

This question is in the vein of my former question Fast Comparing of the Volume of Simplices Defined by Sidelengths, but it has a different twist, that may allow for an easier answer:

Questions:

  • Given a non-degenerate simplex, that is defined via its sidelengths, how can the face with the largest "hyper area" be found efficiently and,
  • are there counterexamples to the conjecture, that the vertex with smallest length-sum of adjacent edges isn't contained in the largest face's containing hyperplane?

edit:
calculating the area of each face and then taking the maximum of those values is of course a valid method, but I am hoping for something more efficient because the problems are of very high dimension.
This edit is motivated by the valuable feedback of @IgorRivin.

Improve this question
$\endgroup$
5
  • $\begingroup$ "smallest sum of adjacent edges" => "smallest sum of adjacent edge lengths"? $\endgroup$ Commented Feb 18, 2018 at 16:26
  • $\begingroup$ @JosephO'Rourke yes, of course; thanks for pointing me to it. I will edit accordingly. $\endgroup$ Commented Feb 18, 2018 at 18:10
  • $\begingroup$ The largest hyper area corresponds to the maximal height (distance from the vertex to the opposite face). I am not sure, though, that if the simplex is defined via edges, this helps. $\endgroup$ Commented Feb 19, 2018 at 8:37
  • $\begingroup$ I'm curious: what is the context in which you are given the edge lengths but not explicit vertex coordinates? Comparatively, representing the simplex shape by its edge lengths tends to be fundamentally inaccurate (if represented by floading-point numbers). $\endgroup$ Commented Mar 10 at 20:53
  • $\begingroup$ @DonHatch I have graph with edge weights that are euclidean distance, say coming from measuring distances in field survey, and I don't want to reconstruct coordinates from distances because that would introduce numeric errors unless one is willing to accept intimidating expressions as coordinates $\endgroup$ Commented Mar 12 at 16:10

2 Answers 2

Reset to default
3
$\begingroup$

I am not sure what you mean by "efficiently", but the Cayley-Menger determinant can be used to compute the volume of a face in time $O(d^3),$ and since there are $O(d)$ maximal dimension faces, the maximum can be computed in time $O(d^4).$ As for the second question, do you even know this to be true in three dimensions?

Improve this answer
$\endgroup$
4
  • $\begingroup$ I am well aware of the solution via the Cayley Menger Determinants, but as I am interested in the answer for very high-dimensional simplices, so that $O(d^4)$ is too expensive. The heuristic related to the 2nd part of the question requires only $O(d)$ and would seem strange to me, that no exact algorithm with intermediate complexity should exist. $\endgroup$ Commented Feb 19, 2018 at 4:05
  • $\begingroup$ @ManfredWeis Firstly, I don't see how your conjectural answer is $O(d)$ - looks like $O(d^2\log d).$ Secondly, it is conjectural. Thirdly, life (and mathematics) is full of mysteries. $\endgroup$ Commented Feb 19, 2018 at 5:48
  • 1
    $\begingroup$ @ManfredWeis Fourthly, if you were aware of the Cayley-Menger approach, it would have been both useful and polite to mention it. $\endgroup$ Commented Feb 19, 2018 at 5:53
  • $\begingroup$ please accept my apologies for not mentioning, that I was aware of the solution with the Cayley-Menger determinant; I had assumed, that the link to my former question would be sufficient. My complexity calculation for the heuristic is wrong (I forgot the effort for summing up the distances); that should be $O(d^2)$, namely adding $d$-times $d-1$ distance-values and the calculating the maximum in $O(d)$. I will edit my question to take into account your feedback. $\endgroup$ Commented Feb 19, 2018 at 8:54
1
$\begingroup$

Surprisingly it is possible to determine the largest face of a $d$-simplex in $O((d+2)^3)$ (or more precise: the problem isn't harder than in inverting a $(d+2)\times (d+2)$-matrix, namely the associated Cayley-Menger matrix $\hat{B}$.

I was able to find an efficient solution of the stated problem, when I discovered an online article by G. Westendorp, dated April 2013 A formula for the N-circumsphere of an N-simplex.
In that article one finds an interpretation of the inverse of a Cayley-Menger matrices, $\hat{B}$$^{-1}$, that makes them (at least to me) by orders of magnitudes more interesting, than $\hat{B}$ itself.


I was able to find an efficient solution to the problem, when I read that $\hat{B}$$^{-1}$ contains as entries the diameter and the barycentric coordinates of the simplexe's circum-sphere and center.

The key observation that occured to me was that the barycentric coordinate of a vertex $v$ corresponds to the hyper-volume of the simplex obtained by replacing $v$ with the circum-center. The resulting "center-simplex" contains all edges of the face, that is opposite to $v$, plus $d$ edges of length $r$, the radius of the circum-sphere.

As the same is true for all other simplex-vertices, the relative order of the volumes of the associated "center-simplices" is solely owed to the hyper-area of the "base-face", i.e. the one that doesn't contain the circum-center of the original simplex.

All together the answer to the problem of efficiently determining the largest face of a simplex is:

  • calculate the inverse $\hat{B}$$^{-1}$ of the Cayley-Menger matrix, that is associated with the simplex
  • find in the first row/column the smallest barycentric coordinate $\alpha$ of the circumcenter
  • report the face opposite to the vertex with barycentric weight $\alpha$

All in all it was possible to reduce the complexity by a linear factor, whereas normally, with divide and conquer, it is only possible to replace a linear factor by a logarithmic one.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Isn't it a problem that the ratio of the volume of a "center-simplex" to the area of its "base-face" is the height of the center-simplex (divided by dimension), hence not the same for all faces ? I can imagine (wrongly?) situations where it vanishes or becomes negative... $\endgroup$ Commented Mar 3, 2018 at 14:05
  • $\begingroup$ This wouldn't be the case for the in-center (instead of circumcenter) though. $\endgroup$ Commented Mar 3, 2018 at 14:14
  • $\begingroup$ @BS: yes, therefore I am so amazed that the inverse of the Cayley-Menger matrix provides exactly what is needed for an efficient solution. $\endgroup$ Commented Mar 3, 2018 at 14:56
  • $\begingroup$ Here is a link to a newer article by Houllier that cites Westendorp: n-Simplex circumsphere $\endgroup$ Commented Nov 5 at 9:40

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.