On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space. (English) Zbl 0616.52009

A convex k-sided polygonal area B moving (translations and rotations) amidst polygonal areas \(A_ 1,...,A_ m\) composed of a total number of n straight line segments is allowed to have border points incident to such a straight line segment (a touching contact), but not allowed to have common points with the interior of one of these polygonal areas \(A_ 1,...,A_ m\). In this paper estimates of the number of positions of B are given where B makes simultaneously three touching contacts with the areas \(A_ 1,...,A_ m\). Such a position is called a critical free contact. It is shown that the number of critical free contacts is O(kn \(\lambda\) \({}_ s(kn))\) where \(\lambda_ s\) is an almost linear functions, and that there exists an example of areas \(B,A_ 1,...,A_ m\) where the number of critical free contacts is \(\Omega (k^ 2n^ 2)\). The applications of these results to the design of motion-planning algorithms is described in the paper of K. Kedem and the second author [”An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space” (Techn. Report 253, Comput. Sci. Dep., Courant Institute) (1986)].
Reviewer: R.Klette


52A37 Other problems of combinatorial convexity
52Bxx Polytopes and polyhedra
68Q25 Analysis of algorithms and problem complexity
68R99 Discrete mathematics in relation to computer science
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI EuDML


[1] M. Atallah, Dynamic computational geometry,Proceedings of the 24th Symposium on Foundations of Computer Science, 92-99, 1983.
[2] S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes,Combinatorica6 (1986), 175-201. · Zbl 0636.05003 · doi:10.1007/BF02579170
[3] K. Kedem and M. Sharir, An Efficient Motion-Planning Algorithm for a Convex Polygonal Object in Two-Dimensional Polygonal Space, Technical Report 253, Computer Science Department, Courant Institute, 1986. · Zbl 0688.68039
[4] K. Kedem, R. Livne, J. Pach, and M. Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles,Discrete Comput. Geom.1 (1986), 59-71. · Zbl 0594.52004 · doi:10.1007/BF02187683
[5] D. Leven and M. Sharir, An efficient and simple motion-planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers,Proceedings of the ACM Symposium on Computational Geometry, 221-227, 1985 (also to appear inJ. Algorithms).
[6] D. Leven and M. Sharir, Planning a Purely Translational Motion for a Convex Object in Two-Dimensional Space Using Generalized Voronoi Diagrams, Technical Report 34/85, The Eskenasy Institute of Computer Science, Tel Aviv University, 1985 (also to appear inDiscrete Comput. Geom.). · Zbl 0606.52002
[7] J. T. Schwartz and M. Sharir, On the piano movers’ problem: I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers,Comm. Pure Appl. Math.36 (1983), 345-398. · Zbl 0554.51007 · doi:10.1002/cpa.3160360305
[8] M. Sharir, Almost Linear Upper Bounds on the Length of Generalized Davenport-Schinzel Sequences, Technical Report 29/85, The Eskenasy Institure of Computer Science, Tel-Aviv University, 1985 (also to appear inCombinatorica7 (1987).)
[9] M. Sharir, Improved Lower Bounds on the Length of Davenport-Schinzel Sequences, Technical Report 204, Computer Science Department, Courant Institute, 1986. · Zbl 0672.05015
[10] E. Szemeredi, On a problem by Davenport and Schinzel,Acta Arith.25 (1974), 213-224. · Zbl 0291.05003
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.