Cutting a convex polyhedron out of a sphere (Q659695)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cutting a convex polyhedron out of a sphere |
scientific article |
Statements
Cutting a convex polyhedron out of a sphere (English)
0 references
24 January 2012
0 references
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\).
0 references
approximation algorithm
0 references
guillotine cut
0 references
polyhedron cutting
0 references