Vertical decompositions for triangles in 3-space

ABSTRACT

We prove that, for any constant &egr;>0, the complexity of the vertical decomposition of a set of n triangles in three-dimensional space is O(n2+&egr;+K), where K is the complexity of the arrangement of the triangles. For a single cell the complexity of the vertical decomposition is shown to be O(n2+&egr;). These bounds are almost tight in the worst case. We also give a deterministic output-sensitive algorithm for computing the vertical decomposition that runs in O(n2logn+Vlogn) time, where V is the complexity of the decomposition. The algorithm is reasonably simple (in particular, it tries to perform as much of the computation in two-dimensional spaces as possible) and thus is a good candidate for efficient implementations.

REFERENCES

• 1: P. K. Agarwal , M. Sharir , P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel Sequences, Journal of Combinatorial Theory Series A, v.52 n.2, p.228-274, Nov. 1989 [doi>10.1016/0097-3165(89)90032-0]
• 2: B. Aronov and M. Sharir. Triangles in space or building (and analyzing) castles in the air. Combinatorica, 10(2):137-173, 1990.
• 3: Boris Aronov , Micha Sharir, Castles in the air revisited, Proceedings of the eighth annual symposium on Computational geometry, p.146-156, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142710]
• 4: J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput., C-28:643-647, 1979.
• 5: Bernard Chazelle, Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM Journal on Computing, v.13 n.3, p.488-507, August 1984 [doi>10.1137/0213031]
• 6: Bernard Chazelle, An optimal convex hull algorithm and new results on cuttings (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.29-38, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185345]
• 7: Bernard Chazelle , Herbert Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Journal of the ACM (JACM), v.39 n.1, p.1-54, Jan. 1992 [doi>10.1145/147508.147511]
• 8: Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.179-193, July 11-15, 1989
• 9: 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]
• 10: B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Combinatorica, 10(3):229-249, 1990.
• 11: Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
• 12: Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
• 13: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 14: Michael T. Goodrich , Roberto Tamassia, Dynamic trees and dynamic point location, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.523-533, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103472]
• 15: L. J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In Proc. 19th A nnu. IEEE $ympos. Found. Comput. $ci., Lecture Notes in Computer Science, pages 8-21, 1978.
• 16: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 17: D. Halperin and M. Sharir. Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment. In Proc. 3~th Annu. Sympos. on Foundations of Computer Science, pages 382-391, 1993.
• 18: S. Hart and M. Sharir. Nonlinearity of Davenport- Schinzel sequences and of generalized path compression schemes. In Proc. 25th Annu. IEEE Sympos. Found. Comput. Sci., pages 313-319, 1984.
• 19: D. Haussler and E. Welzl. Epsilon-ncts and simplex range queries. Discrete Comput. Geom., 2:127-151, 1987.
• 20: J. Hershberger, Finding the upper envelope of n line segments in O(n log n) time, Information Processing Letters, v.33 n.4, p.169-174, December 1989 [doi>10.1016/0020-0190(89)90136-1]
• 21: Jiří Matoušek, Range searching with efficient hierarchical cuttings, Proceedings of the eighth annual symposium on Computational geometry, p.276-285, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142732]
• 22: Ketan Mulmuley, Hidden surface removal with respect to a moving view point, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.512-522, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103471]
• 23: Ketan Mulmuley, Randomized multidimensional search trees: further results in dynamic sampling (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.216-227, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185371]
• 24: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 25: Franco P. Preparata , Roberto Tamassia, Efficient point location in a convex spatial cell-complex, SIAM Journal on Computing, v.21 n.2, p.267-280, April 1992 [doi>10.1137/0221020]
• 26: M. Sharir. Almost tight upper bounds for lower envelopes in higher dimensions. In Proc. 3Jth Annu. iEEE Sympos. Found. Comput. $ci. (FOC$ 93), pages 498-507, 1993.
• 27: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 28: 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:
  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.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Theory, Verification