New bounds for lower envelopes in three dimensions, with applications to visibility in terrains

ABSTRACT

We consider the problem of bounding the complexity of the lower envelope of n surface patches in 3-space, all algebraic of constant maximum degree, and bounded by algebraic arcs of constant maximum degree, with the additional property that the interiors of any triple of these surfaces intersect in at most two points. We show that the number of vertices on the lower envelope of n such surface patches is On²˙2^{clog n} for some constant c depending on the shape and degree of the surface patches. We apply this result to obtain an upper bound on the combinatorial complexity of the “lower envelope” of the space of all rays in 3-space that lie above a given polyhedral terrain K with n edges. This envelope consists of all rays that touch the terrain (but otherwise lie above it). We show that the combinatorial complexity of this ray-envelope is On²˙2^{clog n} for some constant c; in particular, there are at most that many rays that pass above the terrain and touch it in 4 edges. This bound, combined with the analysis of de Berg et al. [2], gives an upper bound (which is almost tight in the worst case) on the number of topologically-different orthographic views of such a terrain.

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: M. de Berg, D. H alperin, M. Overmars and M. van Kreveld, Sparse arrangements and the number of vie. ws of polyhedral scenes, manuscript, 1991.
• 3: 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
• 4: 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]
• 5: 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]
• 6: 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]
• 7: Richard Cole , Micha Sharir, Visibility problems for polyhedral terrains, Journal of Symbolic Computation, v.7 n.1, p.11-30, Jan. 1989 [doi>10.1016/S0747-7171(89)80003-3]
• 8: D. Halperin, Algorithmic Motion Planning via Arrangements of Curves and of Surfaces, Ph.D. Dissertation, Computer Science Department, Tel Aviv University, July 1992.
• 9: D. Halperin and M. Sharir, Near-quadratic bounds for the motion planning problem for a polygon in a }polygonal environment, in preparation.
• 10: 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]
• 11: J. Pach and M. Sharir, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis, Discrete Comput. Geom. 4 (1989), 291- 3(}f9.
• 12: Marco Pellegrini, On lines missing polyhedral sets in 3-space, Proceedings of the ninth annual symposium on Computational geometry, p.19-28, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.160990]
• 13: J. T. Schwartz , M. Sharir, On the two-dimensional Davenport-Schinzel problem, Journal of Symbolic Computation, v.10 n.3-4, p.371-393, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80070-3]
• 14: M. Sharir, On k-sets in arrangements of curves and surfaces, Discrete Compu~. Geom. 6 (1991), 593- 613.
• 15: M. Shark, Almost tight upper bounds for lower envelopes in higher dimensions, manuscript, 1993.
• 16: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996

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:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Boundary representations
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Raytracing

General Terms:
Algorithms, Theory, Verification