Separability of pairs of polygons through single translations

Abstract

SUMMARY Let P = { p 1 , …, p n } and Q = { q 1 ,…, q m } be two simple polygons in the plane with non-intersecting interiors, the vertices of which are specified by their cartesian coordinates in order. The translation separability query asks whether there exists a direction in which P can be translated by an arbitrary distance without colliding with Q . It is shown that all directions that admit such a motion can be computed in O ( n log m ) time, where n > m , thus improving the previous complexity of O (nm) established for this problem. In designing this algorithm a polygon partitioning technique is introduced that may find application in other geometric problems. The algorithm presented in this paper solves a simplified version of the grasping problem in robotics. Given a description of a robot hand and a set of objects to be manipulated, the robot must determine which objects can be grasped. The solution given here assumes a two-dimensional world, a hand without an arm, and grasping under translation only.