largest volume tetrahedron in a convex polyhedron

Viewed 286

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

1 Answers
Related