Abstract
Consider the problem of moving a closed chain ofn links in two or more dimensions from one given configuration to another. The links have fixed lengths and may rotate about their endpoints, possibly passing through one another. The notion of a “line-tracking motion” is defined, and it is shown that when reconfiguration is possible by any means, it can be achieved byO(n) line-tracking motions. These motions can be computed inO(n) time on real RAM. It is shown that in three or more dimensions, reconfiguration is always possible, but that in dimension two this is not the case. Reconfiguration is shown to be always possible in two dimensions if and only if the sum of the lengths of the second and third longest links add to at most the sum of the lengths of the remaining links. AnO(n) algorithm is given for determining whether it is possible to move between two given configurations of a closed chain in the plane and, if it is possible, for computing a sequence of line-tracking motions to carry out the reconfiguration.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. Canny.Complexity of Robotic Motion Planning. (ACM Doctoral Dissertation Award, 1987). MIT Press, Cambridge, MA, 1988.
G. M. Crippen and T. F. Havel.Distance Geometry and Molecular Conformation. Wiley, New York, 1988.
J.-C. Hausmann, Sur la topologie des bras articulés. In S. Jackowski, B. Oliver, and K. Pawałowski, editors,Algebraic Topology, Poznań, 1989, pp. 146–159 (Proceedings of a conference held in Poznań, Poland, June 22–27, 1989.) Lecture Notes in Mathematics, vol. 1474, Springer-Verlag, Berlin, 1991.
J. Hopcroft, D. Joseph, and S. Whitesides. Movement problems for 2-dimensional linkages.SIAM J. Comput., 13:610–629, 1984.
J. Hopcroft, D. Joseph, and S. Whitesides. On the movement of robot arms in 2-dimensional bounded regions.SIAM J. Comput., 14:315–333, 1985.
B. Jaggi. Punktmengen mit Vorgeschriebenen Distanzen und Ihre Konfigurationsraüme. Inauguraldissertation, Bern, 1992.
D. Joseph and W. H. Plantinga. On the complexity of reachability and motion planning questions.Proceedings of the Symposium on Computational Geometry, pp. 62–66, June 1985.
V. Kantabutra. Motions of a short-linked robot arm in a square.Discrete Comput. Geom., 7:69–76, 1992.
V. Kantabutra and S. R. Kosaraju, New algorithms for multilink robot arms.J. Comput. System Sci., 32:136–153, 1986.
W. Lenhart and S. Whitesides. Turning a polygon inside-out.Proceedings of the 3rd Canadian Conference on Computational Geometry, pp. 66–69, August 1991.
W. Lenhart and S. Whitesides. Reconfiguration with line tracking motions.Proceedings of the 4th Canadian Conference on Computational Geometry, pp. 198–203, August 1992.
J. Reif. Complexity of the mover's problem and generalizations.Proceedings of the 20th Symposium on the Foundations of Computer Science, pp. 421–427, 1979.
J. Schwartz and M. Sharir. On the “piano mover's” problem, II. General techniques for computing topological properties of real algebraic manifolds.Adv. in Appl. Math., 4:298–351, 1983.
J. Schwartz and C. Yap, editors.Algorithmic and Geometric Robotics. Erlbaum, Hillsdale, NJ, 1987.
J. Schwartz, C. Yap, and J. Hopcroft, editors.Planning, Geometry and Complexity of Robot Motion. Ablex, Norwood, NJ, 1987.
S. Whitesides. Algorithmic issues in the geometry of planar linkage movement.Austral. Comput. J., Special Issue on Algorithms, 24(2):42–50, 1992.
S. Whitesides and R. Zhao. On the placement of euclidean trees. Technical Report TR-SOCS-89.03. School of Computer Science, McGill University, 1989.
Author information
Authors and Affiliations
Additional information
The research of the second author was partially supported by an NSERC operating grant.
Rights and permissions
About this article
Cite this article
Lenhart, W.J., Whitesides, S.H. Reconfiguring closed polygonal chains in Euclideand-space. Discrete Comput Geom 13, 123–140 (1995). https://doi.org/10.1007/BF02574031
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574031