Hostname: page-component-7b7567c8c-48dgx Total loading time: 0 Render date: 2026-11-18T00:42:31.030Z Has data issue: false hasContentIssue false

Separability of pairs of polygons through single translations‡

Published online by Cambridge University Press:  09 March 2009

Summary

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(nlogm) 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.

Information

Type
Article
Copyright
Copyright © Cambridge University Press 1987

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable