Cutting cycles of rods in space: hardness and approximation

ABSTRACT

We study the problem of cutting a set of rods (line segments in ℝ³) 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.

REFERENCES

• 1: Boris Aronov , Vladlen Koltun , Micha Sharir, Cutting Triangular Cycles of Lines in Space, Discrete & Computational Geometry, v.33 n.2, p.231-247, February 2005 [doi>10.1007/s00454-004-1123-5]
• 2: Mark de Berg, Ray Shooting, Depth Orders and Hidden Surface Removal, Springer-Verlag New York, Inc., Secaucus, NJ, 1993
• 3: Mark de Berg , Chris Gray, Vertical ray shooting and computing depth orders for fat objects, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.494-503, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109612]
• 4: M. de Berg, D. Halperin, M. H. Overmars, J. Snoeyink, and M. J. van Kreveld. Efficient ray shooting and hidden surface removal. Algorithmica, 12:30--53, 1994.
• 5: Mark de Berg , Mark Overmars , Otfried Schwarzkopf, Computing and Verifying Depth Orders, SIAM Journal on Computing, v.23 n.2, p.437-446, April 1994 [doi>10.1137/S0097539791223747]
• 6: Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Richard Pollack , Raimund Seidel , Micha Sharir , Jack Snoeyink, Counting and cutting cycles of lines and rods in space, Computational Geometry: Theory and Applications, v.1 n.6, p.305-323, June 1992 [doi>10.1016/0925-7721(92)90009-H]
• 7: Guy Even , Joseph Seffi Naor , Satish Rao , Baruch Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Journal of the ACM (JACM), v.47 n.4, p.585-616, July 2000 [doi>10.1145/347476.347478]
• 8: G. Even, J. S. Naor, B. Schieber, and M. Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20:151--174, 1998.
• 9: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 10: M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics, 32:826--834, 1977.
• 11: S. Har-Peled and M. Sharir. Online point location in planar arrangements and its applications. Discrete & Computational Geometry, 26:19--40, 2001.
• 12: Matthew J. Kaltz, 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects, Computational Geometry: Theory and Applications, v.8 n.6, p.299-316, Nov. 1997 [doi>10.1016/S0925-7721(96)00027-2]
• 13: Matthew J. Katz , Mark H. Overmars , Micha Sharir, Efficient hidden surface removal for objects with small union size, Computational Geometry: Theory and Applications, v.2 n.4, p.223-234, Dec. 1992 [doi>10.1016/0925-7721(92)90024-M]
• 14: Micha Sharir , Mark H. Overmars, A simple output-sensitive algorithm for hidden surface removal, ACM Transactions on Graphics (TOG), v.11 n.1, p.1-11, Jan. 1992 [doi>10.1145/102377.112141]
• 15: San Skulrattanakulchai, 4-edge-coloring graphs of maximum degree 3 in linear time, Information Processing Letters, v.81 n.4, p.191-195, 28 February 2002 [doi>10.1016/S0020-0190(01)00221-6]
• 16: Alexandra Solan, Cutting cylces of rods in space, Proceedings of the fourteenth annual symposium on Computational geometry, p.135-142, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276899]
• 17: Roberto Tamassia, On embedding a graph in the grid with the minimum number of bends, SIAM Journal on Computing, v.16 n.3, p.421-444, June 1987 [doi>10.1137/0216030]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation

General Terms:
Algorithms, Design, Theory