TY - JOUR
T1 - Separability of pairs of polygons through single translations
AU - Sack, Jörg Rüdiger
AU - Toussaint, Godfried T.
N1 - Funding Information:
Recently a growing interest in the development of a theory of movement has been observed. Typically, movability problems arise in such areas as robotics, graphics and VLSI.1 In robotics a task is to move a robot arm carrying an object O through a set of obstacles without any collisions occurring between the arm, O and these obstacles. A primary recognition task is to determine whether such a task is in fact possible. Several researchers have made efforts in that direction.2"15 A robotics problem more closely related to the problem considered in this paper is grasping an object with a robot hand. Ignoring several factors such as forces and friction, and severing the hand from the arm leads to a purely geometrical problem. In particular, if we consider only two dimensional space and model the "hand" and the "object" as two polygons then an interesting * School of Computer Science, Carleton University, Ottawa, Ontario (Canada), K1S5B6. t School of Computer Science, McGill University, Montreal, Quebec (Canada), H3A2K6. tThis research was supported by NSERC under the grant numbers A0332, A9293 and FCAC under grant number EQ1678, and a Killam Senior Research Fellowship awarded to the second author by the Canada Council. A preliminary version of this paper was presented at the 2nd Annual Symposium on Theoretical Aspects of Computer Science, Saarbriicken, West Germany, January 1985.
PY - 1987/1
Y1 - 1987/1
N2 - Let P = {p1, …, pn} and Q = {q1, …, qm} 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.
AB - Let P = {p1, …, pn} and Q = {q1, …, qm} 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.
UR - http://www.scopus.com/inward/record.url?scp=0023238164&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0023238164&partnerID=8YFLogxK
U2 - 10.1017/S0263574700009644
DO - 10.1017/S0263574700009644
M3 - Article
AN - SCOPUS:0023238164
SN - 0263-5747
VL - 5
SP - 55
EP - 63
JO - Robotica
JF - Robotica
IS - 1
ER -