Cutting a convex polyhedron out of a sphere (Q659695): Difference between revisions

For a solid \(S\), a guillotine cut is a plane that intersects \(S\), and its cost is the area of the intersection. Given an \(n\)-vertex polyhedron \(P\) inside a sphere \(S\), an \(O(n^3)\)-time approximation algorithm is describing the guillotine cutting \(P\) out of \(Q\) with \(O(\log^2 n)\)-optimal total cost. The strategy consists of first cutting out of \(Q\) the minimum volume rectangular box \(B\) enclosing \(P\), and then cutting \(P\) out of \(B\).