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(n^2+ε), for any ε>0, where the constant of proportionality depends on ε 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 σ (the so-called zone of σ in the arrangement) is O(n^2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of their boundaries.

References

1. 1.P.K. Agarwal, M. Sharir and P. Shor, Sharp upper and lower bounds for the length of general Davenport Schinzel sequences, J. Combin. Theory, Ser. A. 52 (1989), 228-274.
2. 2.B. Aronov, J. Matou~ek and M. Sharir, On the sum of squares of cell complexities in hyperplane arrangements, Proc. 7th Syrup. on Computational Geometry (1991), pp. 307-313. (To appear in J. Comb. Theory Set. A.)
3. 3.B. Aronov, M. Pellegrini and M. Shark, On the zone of a surface in a hyperplane arrangement, Discrete Cornput. Geom. 9 (1993), 177-186.
4. 4.B. Aronov and M. Sharir, Triangles in space, or building (and analyzing) castles in the air, Combinatorica 10 (1990), 137-173.
5. 5.B. Aronov and M. Sharir, Castles in the air revisited, Proc. 8th A CM Syrup. on Computational Geometry (1992), 146-156. (To appear in Discrete Comput. Geom.)
6. 6.B. Aronov and M. Sharir, Translational motion planning of a convex polyhedron in 3 dimensions, this volume.
7. 7.J. Bochnak, M. Coste and M-F. Roy, Gdomdtrie Algdbrique Rdelle, Springer-Verlag, Berlin 1987.
8. 8.B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir and J. Snoeyink, Computing a single face in an arrangement of line segments and related problems, SIAM J. Computing 22 (1993)(in press).
9. 9.K. Clarkson and P. Shor, Applications of random sampling in computational geometry, II, Discrete Comput. Geom. 4 (1989), 387-421.
10. 10.M. de Berg, L.J. Guibas and D. Halperin, Vertical decompositions for triangles in 3-space, this volume.
11. 11.H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987.
12. 12.H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel and M. Sharir, Arrangements of curves in the plane- Topology, combinatorics, and algorithms, Theoretical Computer Science 92 (1992), 319-336.
13. 13.H. Edelsbrunner, R. Seidel and M. Sharir, On the zone theorem in hyperplane arrangements, SIAM J. Computing 22 (1993), 418-429.
14. 14.L.J. Guibas, M. Sharir and S. Sifrony, On the general motion planning problem with two degrees of freedom, Discrete and Comput. Geom. 4 (1989), 491-521.
15. 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. 16.D. Halperin and M. Sharir, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, Proc. 9th A CM Symp. on Computational Geometry (1993), pp. 11-18. Also to appear in Discrete Comput. Geom.
17. 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. 18.S. Hart and M. Sharir, Nonlinearity of Davenport- Schinzel sequences and of generalized path compression schemes, Combinatorica 6 (1986), 151-177.
19. 19.R. Hartshorne, Algebraic Geometry, Springer-Verlag, New York 1977.
20. 20.M.W. Hirsch, Differential Topology, Springer-Verlag, New York 1976.
21. 21.P. McMullen, The maximum number of faces of a convex polytope, Mathematika 17 (1970), 179-184.
22. 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. 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. 24.J.T. Schwartz and M. Sharir, On the two-dimensional Davenport Schinzel problem, J. Symbolic Computation 10 (1990), 371-393.
25. 25.M. Sharir, On k-sets in arrangements of curves and surfaces, Discrete Comput. Geom. 6 (1991), 593-613.
26. 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

• Computer systems organization

  • Embedded and cyber-physical systems

    • Robotics

• Computing methodologies

  • Artificial intelligence

    • Control methods

      • Robotic planning

    • Planning and scheduling

      • Robotic planning

  • Symbolic and algebraic manipulation

    • Symbolic and algebraic algorithms

      • Algebraic algorithms

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Combinatorial algorithms

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry