Finding a line transversal of axial objects in three dimensions

ABSTRACT

An axial object in E3 is a box or rectangle, all of whose edges are parallel to the coordinate axes. A line transveral of a set of axial objects is a line that intersects every object. We present an algorithm which finds a line transversal, if one exists, in expected linear time. In the process, we generalize a randomized linear programming algorithm, and prove that the set of line transversals of axial objects has a constant number of connected components.

REFERENCES

• AW87: D. Avis , R. Wenger, Algorithms for line transversals in space, Proceedings of the third annual symposium on Computational geometry, p.300-307, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41990]
• CEGS 89: B. Chazelle , H. Edelsbrunner , L. Guibas , M. Sharir, Lines in space-combinators, algorithms and applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.382-393, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73044]
• HT91: Michael E Hohmeyer , Seth J Teller, Stabbing Isothetic Boxes and Rectangles in O(nlgn) Time, University of California at Berkeley, Berkeley, CA, 1991
• MO88: M. McKenna , J. O'Rourke, Arrangements of lines in 3-space: a data structure with applications, Proceedings of the fourth annual symposium on Computational geometry, p.371-380, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73431]
• M91: Nimrod Megiddo. personal communication, 1991
• PS90: M. Pellegrini , P. Shor, Finding stabbing lines in 3-dimensional space, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.24-31, January 28-30, 1991, San Francisco, California, United States
• Pel 90: Marco Pellegrini, Stabbing and ray shooting in 3 dimensional space, Proceedings of the sixth annual symposium on Computational geometry, p.177-186, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98563]
• Pon 91: Carl Ponder. A Search Approach to general Stabbing Problems, Proce~ings of the $d Canadian Conference on Computational Geometry, pages 195-202, 1991.
• RS 90: Raimund Seidel, Linear programming and convex hulls made easy, Proceedings of the sixth annual symposium on Computational geometry, p.211-215, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98570]
• Tel 91: Seth J. Teller , Carlo H. Séquin, Visibility preprocessing for interactive walkthroughs, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.61-70, July 1991

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Theory, Verification