Triangles in space or building (and analyzing) castles in the Air

ABSTRACT

We show that the combinatorial complexity of all non-convex cells in an arrangement of n (possibly intersecting) triangles in 3-space is &Ogr;(n7/3+&dgr;), for any &dgr;>0, and that this bound is almost tight in the worst case. Our bound significantly improves a previous nearly cubic bound of Pach and Sharir. We also present a (nearly) worst-case optimal randomized algorithm for calculating a single cell of the arrangement, analyze some special cases of the problem where improved bounds (and better algorithms) can be obtained, and describe applications of our results to translational motion planning for polyhedra in 3-space.

REFERENCES

• Ch: B. Chazelle, private communication, February 1988.
• CGL: 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]
• Cl: K. Clarkson, "New applications of random sampling in computational geometry," Discrete Corngut. Geom., 2 (1987), pp. 195-222.
• Ed: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EGPPSS: Herbert Edelsbrunner , Leonidas J. Guibas , János Pach , Richard Pollack , Raimund Seidel , Micha Sharir, Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.214-229, July 11-15, 1988
• EGS: H. Edelsbrunner, L. Guibas, and M. Sharir, "The upper envelope of piecewise linear functions: Algorithms and applications," Tech. Report 333, Comp. Sci. Dept., Courant Institute, November 1987 (to appear in Discrete Comput. Geom.).
• EGS2: H. Edelsbrunner , L. J. Guibas , M. Sharir, The complexity of many faces in arrangements of lines of segments, Proceedings of the fourth annual symposium on Computational geometry, p.44-55, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73399]
• EGS3: H. Edelsbrunner, L. Guibas, and M. Sharir, "The complexity of many cells in arrangemeats of planes and related problems," in preparation.
• EOS: 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]
• EW: H Edelsbrunner , E Welzl, On the maximal number of edges of many faces in an arrangement, Journal of Combinatorial Theory Series A, v.41 n.2, p.159-166, March 1986 [doi>10.1016/0097-3165(86)90078-6]
• HS: 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]
• HW: D. Haussler and E. Welzl, "Epsilon nets and simplex range queries," Discrete Comput. Geom., pp. 12%151.
• PS: J. Pach and M. Sharir, "The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: combinatorial analysis," Tech. Report 279, Comp. Sci. Dept., Courant Institute, March 1987 (to appear in Discrete Comput. Geom.).
• PSS: R. Pollack , M. Sharir , S. Sifrony, Separating two simple polygons by a sequence of translations, Discrete & Computational Geometry, v.3 n.2, p.123-136, Jan, 1988 [doi>10.1007/BF02187902]
• SS: M. Sharir , S. Sifrony, Coordinated motion planning for two independent robots, Proceedings of the fourth annual symposium on Computational geometry, p.319-328, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73426]
• ST: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• WS: Ady Wiernik , Micha Sharir, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, Discrete & Computational Geometry, v.3 n.1, p.15-47, Jan., 1988 [doi>10.1007/BF02187894]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional 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; Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Motion
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Edge and feature detection; Region growing, partitioning

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