Cutting cycles of rods in space : Hardness results and approximation algorithms
Boris S. Aronov, de Mt Mark Berg, CM Chris Gray, Elena Mumford · TU/e Research Portal · 2008
We study the problem of cutting a set of rods (line segments in R3) 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(t log t log log t), where t is the size of an optimal solution.