Immobilizing a polytope

From MaRDI portal





[For the entire collection see Zbl 0756.00009.] A given set of points is said to immobilize a polytope if any rigid motion of the polytope forces at least one point of the given set into the interior of the polytope. In this paper it is shown that three points immobilize a triangle if and only if the three orthogonal lines to the boundary of the triangle at each of the three points are concurrent. This characterization is then generalized to simple polygons (with some restrictions on the three given points). On the other hand it is shown that three points are sufficient to immobilize an \(n\)-polygon in general position, and an \(O(n \log (n))\) algorithm is given in order to find such immobilizing set. For some polygons four points are necessary, but it is commented that higher complexity algorithms are still required to find them. A generalization of the previous results to the case of \(d\)- dimensional polytopes is also included: \(d+1\) points are sufficient for polytopes in general position, \(2d\) points are always sufficient and sometimes necessary for some polytopes.











This page was built for publication: Immobilizing a polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4037421)