Skip to Main Content


Feature Column Archive

6. References

Note: There is a strong overlap between issues involving linkages and rigidity questions. Some of the references below reflect this strong tie. There are two traditions in dealing with linkages: one concerned with combinatorial methods and raising issues of complexity in a theoretical framework; the second growing out of the connection between linkages and robot arms. I have tried to include references in both these traditions. Many of the recent papers have appeared as extended abstracts in conference proceedings but are not yet available in fully published final form.

Alt, H. and C. Yap, Algorithmic aspects of motion planning: a tutorial, Part 1, Algorithms Review, 1 (1990) 43-60.

Alt, H. and C. Yap, Algorithmic aspects of motion planning: a tutorial, Part 2, Algorithms Review, 1 (1990) 61-78.

Biedl, T. and E. Demaine, M. Demaine, S. Lazard. A. Lubiw, J. O'Rourke, M Overmars, S. Robbins, I. Streinu, G. Toussaint, S. Whitesides, Locked and unlocked polygonal chains in 3d. Proc. 10th. ACM-SIAM Symposium on Discrete Algorithms, 1999, p. 866-867.

Borcea, C. and Il Streinu, On the number of embeddings of mini ally rigid graphs, preprint.

Bottema, O. and B. Roth, Theoretical Kinematics, North-Holland, Amsterdam, 1979.

Cayley, A. and S. Roberts, On three-bar motion, Proc. London Math. Soc., 7 (1876) 14.

Cayley, A. and S. Roberts, On three-bar motion, Proc. London Math. Soc. 7 (1876) 136.

Connelly, R. and E. Demaine, G. Rote, Straightening polygonal arcs and convexifying polygonal cycles, Discrete and Computational Geometry, to appear.

Connelly, R. and E. Demaine, G. Rote, Infinitesimally locked self-touching linkages with applications to locked trees, preprint.

Gibson, C.G., Marsh,D. and Xiang,Y. An Algorithm to Generate the Transition Curve of the Planar Four-bar Mechanism. Mechanism and Machine Theory, 31
(1996) 381--395.

Gibson, C.G. Elementary Geometry of Algebraic Curves, Cambridge University Press, London, 1998.

Graver, J., Rigidity matroids, SIAM J. Discrete Math., 4 (1991) 355-368.

Graver, J. and B. Servatius, H. Servatius, Combinatorial Rigidity, American Mathematical Society, Providence, 1993.

Graver, J., Counting on Frameworks, Mathematical Association of America, Washington, 2001.

Hartenberg, R. and J. Denavit, Kinematic Synthesis of Linkages, McGraw-Hill, New York, 1964.

Hopcroft, J. and D. Joseph, S. Whitesides, Movement problems for 2-dimensional linkages, SIAM J. Computing 13 (1984) 610-629.

Hopcroft, J. and D. Joseph, S. Whitesides, On the movement of robot arms in 2-dimensional bounded region, SIAM J. Computing 14 (1985) 315-333.

Hrones, J. and G. Nelson, Analysis of the Four-bar Linkage, Wiley, New York, 1951.

Jordan, D. and M. Steiner, Configuration spaces of mechanical linkages, Disc. and Comp. Geometry 22 (1999) 297-315.

Jordan, D. and M. Steiner, Compact surfaces as configuration spaces of mechanical linkages, Israel J. Math. 122 (2001) 175-187.

Joseph, D. and W. Plantinga, On the complexity of reachability and motion planning questions, Proc. 1st. ACM Symp. Comp. Geo., 1985, 315-333.

Kantabutra, V., Motions of a short-linked robot arm in a square, Discrete Comput. Geom. 7 (1992) 69-76.

Kantabutra, V. and S. Kosaraju, New algorithms for multilink robot arms, J. Comput. Sys. Sci., 32 (1986) 136-153.

Kapovich, M. and J. Millson, On the moduli space of polygons in the Euclidean plane, J. of Diff. Geo. 42 (1995) 133-164.

Kapovich, M. and J. Millson, Universality theorems for configuration spaces of planar linkages, preprint, 1998.

Kapovich, M. and J. Millson, Moduli spaces of linkages and arrangements, Advances in geometry, Progr. Math. 172, Birkhauser Boston, Boston, 1999, 237-270.

Kempe, A., How To Draw a Straight Line; A Lecture on Linkages, Macmillan, London, 1877.

King, H., Planar linkages and algebraic sets, Turkish J. Math. 23 (1999) 33-56.

Korein, J., A Geometric Investigation of Reach, MIT Press, Cambridge, 1985.

Laman, G., On graphs and rigid plane skeletal structures, J. Engineering Mathematics 4 (1970) 331-340.

LaTombe, J., Robot Motion Planning, Kluwer Publishers, 1991.

Lenhart, W. and S. Whitesides, Turning a polygon inside out, Proc. 3rd Canadian Conf. Comp. Geo., 1991, 66-69.

Lenhart, W. and S. Whitesides, Reconfiguring closed polygonal chains in Euclidean d-space, Disc. Comput. Geo. 13 (1995) 123-140.

Lenhart, W. and S. Whitesides, Reconfiguration using line tracking motions, Proc. 4th Canadian Conf. Compu. Geometry, 1992, 198-203.

Lovasz, L. and Y. Yemini, On generic rigidity in the plane, SIAM J. Alg. Disc. Methods 3 (1982) 91-98.

Mermoud, O. and M. Steiner, Visualisation of configuration spaces of polygonal linkages, J. for Geo. and Graphics, 4 (2000) 147-157.

Moukarzerl, C. An efficient algorithm for testing the generic rigidity of graphs in the plane, Preprint.

Rademacher, H. and O. Toeplitz, The Enjoyment of Mathematics, Princeton U. Press, Princeton, 1957, Chapter 18, p. 119-129.

Raghavan, M. and B. Roth, Solving polynomial systems for the kinematic analysis and synthesis of mechanisms and robot manipulators, ASME J. Eng. Industry 85B (1995) 298-306.

Recski, A., Matroid Theory and its Applications in Electrical Theory and in Statics, Springer-Verlag, Berlin, 1989.

Roberts, S., On three-bar motion in plane space, Proc. London Math. Soc. 7 (1975) 14-23.

Schwartz, J. and C. Yap, eds., Algorithmic and Geometric Robotics, Erlbaum, Hillsdale, 1987.

Smith, W., Plane mechanisms and the "downhill principle," preprint, 1998.

Streinu, I., A combinatorial approach to planar non-colliding robot arm motion planning, Proceedings 41st Annual Symp. Foundations of Computer Science, IEEE Press, Washington, p. 353-370.

Suzuki, I. and M. Yamashita, Designing Multi-Link Robot Arms in a Convex Polygon, Technical Report TR-90-10-01, Department of Electrical Engineering and CS, U. Wisconsin-Milwaukee, 1991.

Toussaint, G., Simple proofs of a geometric property of four-bar linkages, preprint.

Van Kreveld, M. and J. Snoeyink, S. Whitesides, Folding rulers inside triangles, Proc. 5th Canadian Conf. Comp. Geo., Waterloo, 1993, 1-6.

Van Kreveld, J. Snoeyink, S. Whitesides, Folding Rulers Inside Triangles, Discrete Comput. Geom. 15 (1996) 265-285.

Wampler, C. and A. Morgan, A. Sommese, Complete solution of the nine-point path synthesis problem for four-bar linkages, ASME J. Mechanical Design 114 (1992) 153-159.

Whiteley, W., Motions and stresses of projected polyhedra, Structural Topology 7 (1982) 13-38.

Whiteley, W., Matroids and rigid structures, in Matroid Applications, N. White, (ed.), Encyclopedia of Mathematics and Its Applications, Cambridge U. Press, New York, 1992, p. 1-53.

Whiteley, W., Rigidity and polarity. I. Statics of sheet structures, Geometriae Dedicata 22 (1987) 329-362.

Whiteley, W., Infinitesimally rigid polyhedra. II. Modified spherical frameworks, Trans. AMS, 306 (1988) 115-139.

Whitesides, S., Algorithmic issues in the geometry of planar linkage movement, The Australian Computer J., Special Issue on Algorithms, May, 1992, p. 42-50.

Whitesides, S. and N. Pei, On the reconfiguration of chains, in Proceedings of COCOON, 96, Hong Kong, June, 1996, Lecture Notes in Computer Science, Volume 1090, J. Y. Cai and C. K. Kuen, eds., Springer-Verlag.


  1. Introduction
  2. Some history
  3. Basic ideas
  4. Peaucellier-Lipkin linkage
  5. Sneak preview: carpenter's ruler problems
  6. References