TY - GEN
T1 - Cutting cycles of rods in space
T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms
AU - Aronov, Boris
AU - De Berg, Mark
AU - Gray, Chris
AU - Mumford, Elena
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=58449134854&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58449134854&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:58449134854
SN - 9780898716474
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1241
EP - 1248
BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Y2 - 20 January 2008 through 22 January 2008
ER -