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 -