Castles in the air revisited

ABSTRACT

We show that the total number of faces bounding any single cell in an arrangement of n (d–1)-simplices in IRd is O(nd–1 log n), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational motion planning in polyhedral environments. We then extend our analysis technique to derive other results on complexity in simplex arrangements. For example, we show that the number of vertices in such an arrangement, which are incident to the same cell on more than one “side,” is O(nd-1 log n). We also show that the number of repetitons of a “k-flap,” formed by intersecting d–k simplices, along the boundary of the same cell, summed over all cells and all k-flaps, is O(nd-1 log n). We use this quantity, which we call the excess of the arrangement, to derive bounds on the complexity of m distinct cells of such an arrangement.

REFERENCES

• AA90: Pankaj K. Agarwal , Boris Aronov, Counting facets and incidences, Discrete & Computational Geometry, v.7 n.4, p.359-369, 1992 [doi>10.1007/BF02187848]
• AMS90: 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]
• AS90: B. Aronov and M. Sharir, Triangles in space or building (and analyzing) castles in the air, Combinatorica 10(2)(1990) 137-173.
• AS91: B. Aronov and M. Shark, On the zone of an algebraic surface in a hyperplane arrangement, in Proc. 1991 Workshop on Algorithms and Data Structures, Ottawa, 1991, 13-19.
• CS89: 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]
• E87: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EGPPSS: 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]
• EGS90a: Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, The complexity and construction of many faces in arrangements of lines and of segments, Discrete & Computational Geometry, v.5 n.2, p.161-196, 1990 [doi>10.1007/BF02187784]
• EGS90b: Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir, The complexity of many cells in arrangements of planes and related problems, Discrete & Computational Geometry, v.5 n.2, p.197-216, 1990 [doi>10.1007/BF02187785]
• ESS91: 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]
• GSS89: 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]
• H91: Dan Halperin, On the complexity of a single cell in certain arrangements of surfaces in 3-space (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.314-323, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109683]
• HKS91: Daniel P. Huttenlocher , Klara Kedem , Micha Sharir, The upper envelope of Voronoi surfaces and its applications, Proceedings of the seventh annual symposium on Computational geometry, p.194-203, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109670]
• PS89: J. Pach and M. Sharir, The upper envelope of piecewise hnear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis, Discrete Comput. Geom. 4 (1989), 291-310.
• SS83: J.T. Schwartz and M. Sharir, On the Piano Movers' problem: II. General techniques for computing topological properties of real algebraic manifolds, Advances in Appl. Math. 4 (1983), 298-351.
• SS90: 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]

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory, Verification