IMMOBILIZING A SHAPE
Jurek Czyzowicz, Ivan Stojmenović, Jorge Urrutia · International Journal of Computational Geometry & Applications · 1999
Let shape P be any simply-connected set in the plane, bounded by a Jordan curve, that is not a circular disk. We say that a set of points I on the boundary of P immobilize the shape if any rigid motion of P in the plane causes at least one point of I to penetrate the interior of P. We prove that four points always suffice to immobilize any shape. For a large class of shapes, which includes polygons without parallel edges, three points are sufficient to immobilize. An O(n log n) algorithm is given that finds a set 3 points that immobilize a given polygon without parallel edges. The algorithm becomes linear for convex polygons. Some results are generalized for d-dimensional polytopes, where 2d points are always sufficient and sometimes necessary to immobilize.