Cutting cycles of rods in space: Hardness and approximation

Boris Aronov, Mark De Berg, Chris Gray, Elena Mumford

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 languageEnglish (US)
    Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
    Pages1241-1248
    Number of pages8
    StatePublished - 2008
    Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
    Duration: Jan 20 2008Jan 22 2008

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

    Other

    Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
    CountryUnited States
    CitySan Francisco, CA
    Period1/20/081/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).