×

Castles in the air revisited. (English) Zbl 0805.52005

Let \(T\) be a set of \(n\) \((d-1)\)-simplices in \(\mathbb{R}^ d\), decomposing the space into open \(d\)-dimensional cells and into relatively open \(k\)- faces, \(0\leq k\leq d-1\). The structure defined by these cells and faces is said to be the arrangement \(A(T)\) of \(T\). The authors show that the maximum possible number of boundary faces of any cell in \(A(T)\) is \(O(n^{d-1}\log n)\), which is the first nontrivial upper bound for arbitrary \(d\); it comes within a logarithmic factor of the best-known lower bound of \(\Omega (n^{d-1} \alpha(n))\), where \(\alpha(n)\) denotes the inverse Ackermann function. The paper contains further results, such as the total number \(O(n^{d-1} \log n)\) of vertices incident to the same cell on more than one “side”, or bounds on the complexity of \(m\) distinct cells in \(A(T)\). All these results have applications to motion planning of mechanical systems subject to piecewise-linear “collision- constraints”, such as e.g. a system of polyhedral bodies translating independently in a polyhedral environment, avoiding the obstacles and each other. Moreover, the authors discuss the main challenge lying further ahead in this direction, namely the extension to the general case of motion planning considering collections of \(n\) constraint surfaces of bounded algebraic degree in \(d\)-space, with \(d\) as the number of degrees of freedom of the moving system.

MSC:

52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] P. K. Agarwal and B. Aronov, Counting facets and incidences,Discrete Comput. Geom.7 (1992), 359-369. · Zbl 0747.68092 · doi:10.1007/BF02187848
[2] B. Aronov, J. Matoušek, and M. Sharir, On the sum of squares of cell complexities in hyperplane arrangements,Proc. 7th Symp. on Computational Geometry, 1991, pp. 307-313. To appear inJ. Combin. Theory Ser. A. · Zbl 0799.52009
[3] B. Aronov, M. Pellegrini, and M. Sharir, On the zone of an algebraic surface in a hyperplane arrangement,Discrete Comput. Geom.9 (1993), 177-186. · Zbl 0773.52007 · doi:10.1007/BF02189317
[4] B. Aronov and M. Sharir, Triangles in space or building (and analyzing) castles in the air,Combinatorica10(2) (1990), 137-173. · Zbl 0717.68099 · doi:10.1007/BF02123007
[5] K. Clarkson and P. Shor, Applications of random sampling in computational geometry, II,Discrete Comput. Geom.4 (1989), 387-421. · Zbl 0681.68060 · doi:10.1007/BF02187740
[6] H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir, Arrangements of curves in the plane: topology, combinatorics, and algorithms,Theoret. Comput. Sci.92 (1992), 319-336. · Zbl 0747.68094 · doi:10.1016/0304-3975(92)90319-B
[7] H. Edelsbrunner, L. Guibas, and M. Sharir, The complexity and construction of many faces in arrangements of lines and of segments,Discrete Comput. Geom.5 (1990), 161-196. · Zbl 0691.68035 · doi:10.1007/BF02187784
[8] H. Edelsbrunner, L. Guibas, and M. Sharir, The complexity of many cells in arrangements of planes and related problems,Discrete Comput. Geom.5 (1990), 197-216. · Zbl 0691.68036 · doi:10.1007/BF02187785
[9] H. Edelsbrunner, R. Seidel, and M. Sharir, On the zone theorem for hyperplane arrangements,SIAM J. Comput.22 (1993), 418-429. · Zbl 0778.52007 · doi:10.1137/0222031
[10] L. Guibas, M. Sharir, and S. Sifrony, On the general motion planning problem with two degrees of freedom,Discrete Comput. Geom.4 (1989), 491-521. · Zbl 0685.68049 · doi:10.1007/BF02187744
[11] D. Halperin, On the complexity of a single cell in certain arrangements of surfaces in 3-space,Proc. 7th ACM Symp. on Computational Geometry, 1991, pp. 314-323.
[12] D. Halperin, Algorithmic Motion Planning, via Arrangements of Curves and of Surfaces, Ph.D. Dissertation, Tel Aviv University, August 1992.
[13] D. Huttenlocher, K. Kedem, and M. Sharir, The upper envelope of Voronoi surfaces and its applications,Discrete Comput. Geom.9 (1993), 267-291. · Zbl 0770.68111 · doi:10.1007/BF02189323
[14] 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-310. · Zbl 0734.05054 · doi:10.1007/BF02187732
[15] J. T. Schwartz and M. Sharir, On the piano movers’ problem: II. General techniques for computing topological properties of real algebraic manifodls,Adv. in Appl. Math.4 (1983), 298-351. · Zbl 0554.51008 · doi:10.1016/0196-8858(83)90014-3
[16] J. T. Schwartz and M. Sharir, On the 2-dimensional Davenport-Schinzel problem,J. Symbolic Comput.10 (1990), 371-393. · Zbl 0717.68050 · doi:10.1016/S0747-7171(08)80070-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.