On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space (Q1821354)

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 \textit{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)].