Clever Geek Handbook

The largest volumetric tetrahedron in a convex polyhedron

Given a convex polyhedron, I need to find a faster algorithm for the maximum tetrahedron inscribed in it. I could only think of a brute force O (n ^ 4) solution. I thought if we could find the farthest vertex in a convex polyhedron from a triangle formed using three polyhedron vertices in less than O (n) time using some preprocessing. The volume of this tetrahedron will be maximum with this base of the triangle (the volume of the tetrahedron is 1/3 * base area * height) and for that for the whole triangle I get the maximum volumetric tetrahedron less than O (n ^ 4).

+3


source to share


1 answer


I would expect this probabilistic algorithm to give a tetrahedron with a volume that is at least close to the largest possible value with a high probability:

  • select any three (pairwise different) vertices A,B,C

    from the polyhedron
  • choose a point D

    from the polyhedron that maximizes the volume of the tetrahedron ABCD

    .
  • select a point A'

    from the polyhedron that maximizes the volume of the tetrahedronA'BCD

  • choose from the polyhedron the point B'

    that maximizes the volume of the tetrahedronA'B'CD

  • choose from the polyhedron a point C'

    that maximizes the volume of the tetrahedronA'B'C'D

  • if A==A'

    u B==B'

    and C==C'

    stop with an answer ABCD

    .
  • set A=A'

    , B=B'

    , C=C'

    and continue for 2.


Obviously, this algorithm ends for any finite polyhedron and any initial choice of A, B, C. And if the polytope is not "too symmetric", the algorithm should quickly finish (< O(n^2)

).

Now, by running this algorithm several times (with different random choices A, B, C at step 1) and keeping the largest tetrahedron found so far, the probability of being close or reaching the maximum possible volume will increase.

0


source






More articles:


All Articles