Cutting a Convex Polyhedron Out of a Sphere

Abstract

Given a convex polyhedron $P$ of $n$ vertices inside a sphere $Q$, we give an $O(n^3)$-time algorithm that cuts $P$ out of $Q$ by using guillotine cuts and has cutting cost $O((\log n{)}^2)$ times the optimal.

10 pages