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$
3
  • $\begingroup$ "smallest sum of adjacent edges" => "smallest sum of adjacent edge lengths"? $\endgroup$
    – Joseph O'Rourke
    Commented Feb 18, 2018 at 16:26
  • $\begingroup$ @JosephO'Rourke yes, of course; thanks for pointing me to it. I will edit accordingly. $\endgroup$
    – Manfred Weis
    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$
    – Fedor Petrov
    Commented Feb 19, 2018 at 8:37

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$
    – Manfred Weis
    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$
    – Igor Rivin
    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$
    – Igor Rivin
    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$
    – Manfred Weis
    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$
3
  • $\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$
    – BS.
    Commented Mar 3, 2018 at 14:05
  • $\begingroup$ This wouldn't be the case for the in-center (instead of circumcenter) though. $\endgroup$
    – BS.
    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$
    – Manfred Weis
    Commented Mar 3, 2018 at 14:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .