Cutting cycles of rods in space: hardness and approximation
Boris S. Aronov, Mark de Berg, Chris Gray, Elena Mumford · Symposium on Discrete Algorithms · 2008
We study the problem of cutting a set of rods (line segments in ℝ3) into fragments, using a minimum number of cuts, so that the resulting set of fragments admits a depth order. We prove that this problem is NP-complete, even when the rods have only three distinct orientations. We also give a polynomial-time approximation algorithm with no restriction on rod orientation that computes a solution of size O(τ log τ log log τ), where τ is the size of an optimal solution.