### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 1241-1248 |

Number of pages | 8 |

State | Published - 2008 |

Event | 19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States Duration: Jan 20 2008 → Jan 22 2008 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 19th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | San Francisco, CA |

Period | 1/20/08 → 1/22/08 |

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Cutting cycles of rods in space: Hardness and approximation'. Together they form a unique fingerprint.

## Cite this

Aronov, B., De Berg, M., Gray, C., & Mumford, E. (2008). Cutting cycles of rods in space: Hardness and approximation. In

*Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 1241-1248). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).