Arrangements of lines in 3-space: a data structure with applications

ABSTRACT

Let an arrangement of blue lines in 3-space be fixed, and imagine a movable red line entangled in the arrangement. We show an &Ogr;(n4&agr;(n)) algorithm for building a data structure that permits enumeration of mutually inaccessible classes of such red lines, where &agr;(n) is the inverse Ackermann function. The core of the algorithm is a construction of &Ogr;(n2) 2-D arrangement of hyperbolas, each in &Ogr;(n2&agr;(n)) time.The algorithm is applied to stabbing 3-polytopes, enumerating pairwise-visible face pairs, enumerating 2-D projections of convex 4-polytopes, and other problems, resulting in &Ogr;(n4&agr;(n)) algorithms in each case.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: 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]
• 3: Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
• 4: Dobkin, D., personal communication, August 1987.
• 5: H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
• 6: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 7: H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
• 8: Filliman, P., "Projections of Polytopes," submitted for publication, March 1987.
• 9: Goodman, J., problem session at the AMS Conference on Discrete and Computational Geometry, University of California at Santa Cruz, July 20-26, 1986.
• 10: L Guibas , R Seidel, Computing convolutions by reciprocal search, Proceedings of the second annual symposium on Computational geometry, p.90-99, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10525]
• 11: S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
• 12: Kleiman, S., Laksov, D., "Schubert Calculus," American Math. Monthly 79, (1972), p. 1061-1082.
• 13: Michael McKenna, Worst-case optimal hidden-surface removal, ACM Transactions on Graphics (TOG), v.6 n.1, p.19-28, Jan. 1987 [doi>10.1145/27625.27627]
• 14: Michael McKenna , Raimund Seidel, Finding the optimal shadows of a convex polytope, Proceedings of the first annual symposium on Computational geometry, p.24-28, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323237]
• 15: White, N., "Comments on Goodman's problem on skew lines," unpublished note, May 1987.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement
          Subjects: Projections

General Terms:
Algorithms, Design, Measurement, Performance, Theory