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

We show that the number of critical positions of a convex polygonal objectB moving amidst polygonal barriers in two-dimensional space, at which it makes three simultaneous contacts with the obstacles but does not penetrate into any obstacle isO(kn _s (kn)) for somes6, wherek is the number of boundary segments ofB,n is the number of wall segments, and _s (q) is an almost linear function ofq yielding the maximal number of breakpoints along the lower envelope (i.e., pointwise minimum) of a set ofq continuous functions each pair of which intersect in at mosts points (here a breakpoint is a point at which two of the functions simultaneously attain the minimum). We also present an example where the number of such critical contacts is (k ² n ²), showing that in the worst case our upper bound is almost optimal.Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.