Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-03T05:10:04.683Z Has data issue: false hasContentIssue false
  • English
  • Français

Separability of pairs of polygons through single translations‡

Published online by Cambridge University Press:  09 March 2009

Jörg-Rüdiger Sack  and
Godfried T. Toussaint
Get access Rights & Permissions [Opens in a new window]

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.

Type
Article
Information
Robotica , Volume 5 , Issue 1 , January 1987 , pp. 55 - 63
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.)

References

1.Guibas, L.J. and Yao, F.F., “On translating a set of rectangles” Proceedings 12th Annual ACM Symposium on Theory of Computing (1980) pp. 154–160.Google Scholar
2.Hopcroft, J.E., Joseph, D.A. and Whitesides, S.H., “On the movement of robot arms in 2-dimensional bounded regions”, Proceedings 23rd Annual Symposium on Foundations of Computer Science (1982) pp. 280–289.Google Scholar
3.Lozano-Perez, T. and Wesley, M., “An algorithm for planning collision-free paths among polyhedral obstacles” Comm. ACM. 22, 421–427 (1979).CrossRefGoogle Scholar
4.Lozano-Perez, T., “Automatic planning of manipulator transfer movements” IEEE Trans. Syst., Man., Cybern. SMC11, 681–198 (1981).Google Scholar
5.Moravec, H.P., “Obstacle avoidance and navigation in the real world by a seeing robot rover” Stanford University Rech Rep., AIM-349 (09 1980).Google Scholar
6.Reif, J., “Complexity of the movers' problem and generalizations” Proceedings 20th Annual Symposium on Foundations of Computer Science (1979) pp. 421–427.Google Scholar
7.Schwartz, J.T. and Sharir, M., “On the piano movers' problem: I. The special case of a rigid polygonal body moving amidst polygonal barriers” Comm. Pure Appl. Math. XXXVI, 345–398 (1983).CrossRefGoogle Scholar
8.Schwartz, J.T. and Sharir, M., “On the piano movers' problem: II. General techniques for computing topological properties of real algebraic manifolds” Adv. Appl. Math. 4, 298–351 (1983).CrossRefGoogle Scholar
9.Schwartz, J.T. and Sharir, M., “On the piano movers' problem: III. Coordinating the motion of several independent bodies: The special case of circular bodies moving amidst polygonal barriers” Robotics Research 2, No. 3, 46–75 (Fall, 1983).CrossRefGoogle Scholar
10.Schwartz, J.T. and Sharir, M., “On the piano movers' problem: IV. Various decomposable two-dimensional motion-planning problems” Comm. Pure Appl. Math. XXXVII, 479–493 (1984).Google Scholar
11.Schwartz, J.T. and Sharir, M., “On the piano movers' problem: V. The case of a rod moving in three-dimensional space amidst polyhedral obstacles” Comm. Pure Appl. Math. XXXVII, 815–848 (1984).CrossRefGoogle Scholar
12.Udupa, S.M., “Collision detection and avoidance in computer controlled manipulators” Proceedings IJACI-5, MIT, Cambridge, MA. (08 1977) pp. 737–748.Google Scholar
13.Toussaint, G.T. and Sack, J.-R., “Some new results on moving polygons in the plane” Proceedings Robotic Intelligence and Productivity Conference, Detroit,MI. (11 1983) pp. 158–163.Google Scholar
14.Widdoes, C., “A heuristic collision avoider for the Stanford robot arm” Stanford CS Memo 227 (06 1974).Google Scholar
15.Yap, C.K., “Motion planning for two discs” Tech. Rept. Courant Institute, N.Y.U., (1983).Google Scholar
16.Toussaint, G.T., “Movable separability of sets” In: Computational Geometry (Ed. Toussaint, G.T.) (North Holland, Amsterdam, 1985).Google Scholar
17.Whitesides, S., “Computational geometry and spatial planning” In: Computational Geometry (Ed. Toussaint, G.T.) North Holland, Amsterdam, 1985).Google Scholar
18.Toussaint, G.T. and ElGindy, H., “Separation of two monotone polygons in linear time” Robotica 2, 215–220 (1984).CrossRefGoogle Scholar
19.Jarvis, R. A., “On the identification of the convex hull of a finite set of points in the plane” Information Processing Letters 2, 18–21 (1973).CrossRefGoogle Scholar
20.Avis, D., ElGindy, H. and Seidel, R., “Simple on-line algorithms for convex polygons” In: Computational Geometry (Ed. Toussaint, G.T.) (North Holland, Amsterdam, 1985).Google Scholar
21.ElGindy, H., “An efficient algorithm for computing the weak visibility polygon from an edge in simple polygons” preliminary version (McGill University, Montréal, Canada, 01 1984).Google Scholar
22.Lee, D.T. and Lin, A., “Computing the visibility polygon from an edge” Tech. Rept. 84–02–FC-01, Northwestern University, Evanston, Ill. (01, 1984).Google Scholar
23.Chazelle, B. and Guibas, L.J., “Visibility and intersection problems in plane geometry” Proceedings of the Symposium on Computational Geometry, Baltimore (1985) pp. 135–146.Google Scholar
24.Preparata, F.P. and Shamos, M.I., Computational Geometry (Springer Verlag, Heidelberg, New York, 1985).CrossRefGoogle Scholar
25.Kirkpatrick, D., “Optimal search in planar subdivisions” SIAM J. Comp. 12, No. 1, 28–35 (02, 1983).CrossRefGoogle Scholar
26.Chvátal, V., “A combinatorial theorem in the plane geometry” J. Combinatorial Theory B 18, 39–41 (1975).CrossRefGoogle Scholar
27.Rappaport, D. and Toussaint, G.T., “A simple linear hidden-line algorithm for star-shaped polygons” Pattern Recognition Letters 3, 35–39 (01, 1985).CrossRefGoogle Scholar
28.Toussaint, G.T., “A historic note on convex hull finding algorithms” Pattern Recognition Letters 3, pp. 21–28 (01, 1985).CrossRefGoogle Scholar
29.Toussaint, G.T., “Shortest path solves translation separability of polygons” Tech. Rept. SCS-8.27, School of Computer Science, McGill University (10, 1985).Google Scholar