Almost tight upper bounds for the single cell and zone problems in three dimensions

ABSTRACT

We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement of n low-degree algebraic surface patches in 3-space. We show that this complexity is O(n2+&egr;), for any &egr;>0, where the constant of proportionality depends on &egr; and on the maximum degree of the given surfaces and of their boundaries. This extends several previous results, almost settles a 7-year-old open problem, and has applications to motion planning of general robot systems with three degrees of freedom. As a corollary of the above result, we show that the overall complexity of all the three-dimensional cells of an arrangement of n low-degree algebraic surface patches, intersected by an additional low-degree algebraic surface patch &sgr; (the so-called zone of &sgr; in the arrangement) is O(n2+&egr;), for any &egr;>0, where the constant of proportionality depends on &egr; and on the maximum degree of the given surfaces and of their boundaries.

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: Boris Aronov , Jiří Matoušek , Micha Sharir, On the sum of squares of cell complexities in hyperplane arrangements, Proceedings of the seventh annual symposium on Computational geometry, p.307-313, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109682]
• 3: Boris Aronov , Marco Pellegrini , Micha Sharir, On the zone of a surface in a hyperplane arrangement, Discrete & Computational Geometry, v.9 n.2, p.177-186, 1993 [doi>10.1007/BF02189317]
• 4: B. Aronov and M. Sharir, Triangles in space, or building (and analyzing) castles in the air, Combinatorica 10 (1990), 137-173.
• 5: 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]
• 6: B. Aronov and M. Sharir, Translational motion planning of a convex polyhedron in 3 dimensions, this volume.
• 7: J. Bochnak, M. Coste and M-F. Roy, Gdomdtrie Algdbrique Rdelle, Springer-Verlag, Berlin 1987.
• 8: Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir , Jack Snoeyink, Computing a face in an arrangement of line segments and related problems, SIAM Journal on Computing, v.22 n.6, p.1286-1302, Dec. 1993 [doi>10.1137/0222077]
• 9: 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]
• 10: M. de Berg, L.J. Guibas and D. Halperin, Vertical decompositions for triangles in 3-space, this volume.
• 11: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 12: Herbert Edelsbrunner , Leonidas Guibas , János Pach , Richard Pollack , Raimund Seidel , Micha Sharir, Arrangements of curves in the plane—topology, combinatorics, and algorithms, Theoretical Computer Science, v.92 n.2, p.319-336, 20 Jan. 1992 [doi>10.1016/0304-3975(92)90319-B]
• 13: Herbert Edelsbrunner , Raimund Seidel , Micha Sharir, On the zone theorem for hyperplane arrangements, SIAM Journal on Computing, v.22 n.2, p.418-429, April 1993 [doi>10.1137/0222031]
• 14: L. J. Guibas, On the general motion-planning problem with two degrees of freedom, Discrete & Computational Geometry, v.4 n.5, p.491-521, 1989 [doi>10.1007/BF02187744]
• 15: D. Halperin, Algorithmic Motion Planning via Arrangements of Curves and of Surfaces, Ph.D. Dissertation, Computer Science Department, Tel Aviv University, July 1992.
• 16: Dan Halperin , Micha Sharir, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, Proceedings of the ninth annual symposium on Computational geometry, p.11-18, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.160989]
• 17: D. Halperin and M. Sharir, Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment, Proc. $dth IEEE Syrup. on Foundations of Computer Science (1993), pp. 382-391.
• 18: 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]
• 19: R. Hartshorne, Algebraic Geometry, Springer-Verlag, New York 1977.
• 20: M.W. Hirsch, Differential Topology, Springer-Verlag, New York 1976.
• 21: P. McMullen, The maximum number of faces of a convex polytope, Mathematika 17 (1970), 179-184.
• 22: 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-309.
• 23: R. Pollack and M.F. Roy, On the number of cells defined by a set of polynomials, C.R. Acad. Sci. Paris, t. 316, S~rie I (1993), 573-577.
• 24: 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]
• 25: M. Sharir, On k-sets in arrangements of curves and surfaces, Discrete Comput. Geom. 6 (1991), 593-613.
• 26: M. Sharir, Almost tight upper bounds for lower envelopes in higher dimensions, Proc. $dth IEEE Syrup. on Foundations of Computer Science (1993), pp. 498- 507. Also to appear in Discrete Comput. Geom.

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
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory, Verification