Separability of pairs of polygons through single translations

Jörg Rüdiger Sack, Godfried T. Toussaint

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)55-63
Number of pages9
Issue number1
StatePublished - Jan 1987

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • General Mathematics
  • Computer Science Applications


Dive into the research topics of 'Separability of pairs of polygons through single translations'. Together they form a unique fingerprint.

Cite this