Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 

 

Planar linkages following a prescribed motion


Authors: Matteo Gallet, Christoph Koutschan, Zijia Li, Georg Regensburger, Josef Schicho and Nelly Villamizar
Journal: Math. Comp. 86 (2017), 473-506
MSC (2010): Primary 70B15, 68W30, 70G55, 20G20, 16Z05, 14P05, 12Y05
DOI: https://doi.org/10.1090/mcom/3120
Published electronically: April 13, 2016
MathSciNet review: 3557808
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Designing mechanical devices, called linkages, that draw a given plane curve has been a topic that interested engineers and mathematicians for hundreds of years, and recently also computer scientists. Already in 1876, Kempe proposed a procedure for solving the problem in full generality, but his constructions tend to be extremely complicated. We provide a novel algorithm that produces much simpler linkages, but works only for parametric curves. Our approach is to transform the problem into a factorization task over some noncommutative algebra. We show how to compute such a factorization, and how to use it to construct a linkage tracing a given curve.


References [Enhancements On Off] (What's this?)

  • [1] Timothy G. Abbott, Generalizations of Kempe's universality theorem,
    Master's thesis, Massachusetts Institute of Technology, 2008.
    Available at http://web.mit.edu/tabbott/www/papers/mthesis.pdf.
  • [2] Wilhelm Blaschke and Hans R. Müller,
    Ebene Kinematik,
    Verlag von R. Oldenbourg, München, 1956.
  • [3] Jacek Bochnak, Michel Coste, and Marie-Françoise Roy, Real algebraic geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 36, Springer-Verlag, Berlin, 1998. Translated from the 1987 French original; Revised by the authors. MR 1659509
  • [4] O. Bottema and B. Roth, Theoretical kinematics, North-Holland Series in Applied Mathematics and Mechanics, vol. 24, North-Holland Publishing Co., Amsterdam-New York, 1979. MR 533960
  • [5] Robert Connelly and Erik D. Demaine, Geometry and topology of polygonal linkages,
    In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, second edition, Chapman & Hall/CRC, Boca Raton, FL, 2004, pp. 197-218.
  • [6] Erik D. Demaine and Joseph O’Rourke, Geometric folding algorithms, Cambridge University Press, Cambridge, 2007. Linkages, origami, polyhedra. MR 2354878
  • [7] Xiaoshan Gao and Changcai Zhu, Automated generation of Kempe linkage and its complexity, J. Comput. Sci. Tech. 14 (1999), no. 5, 460–467. MR 1736726, https://doi.org/10.1007/BF02948787
  • [8] Xiao-Shan Gao, Chang-Cai Zhu, Shang-Ching Chou, and Jian-Xin Ge, Automated generation of Kempe linkages for algebraic curves and surfaces, Mechanism and Machine Theory 36 (2001), no. 9, 1019-1033.
  • [9] Gábor Hegedüs, Josef Schicho, and Hans-Peter Schröcker, Construction of overconstrained linkages by factorization of rational motions,
    In Jadran Lenarčič and Manfred Husty, editors, Latest Advances in Robot Kinematics, Springer Netherlands, 2012, pp. 213-220.
  • [10] Gábor Hegedüs, Josef Schicho, and Hans-Peter Schröcker, Factorization of Rational Curves in the Study Quadric,
    Mechanism and Machine Theory 69 (2013), 142-152.
  • [11] Manfred L. Husty and Hans-Peter Schröcker, Kinematics and algebraic geometry,
    In J. Michael McCarthy, editor, 21st Century Kinematics, Springer London, 2013, pp. 85-123.
  • [12] D. Jordan and M. Steiner, Configuration spaces of mechanical linkages, Discrete Comput. Geom. 22 (1999), no. 2, 297–315. MR 1698549, https://doi.org/10.1007/PL00009462
  • [13] Michael Kapovich and John J. Millson, Universality theorems for configuration spaces of planar linkages, Topology 41 (2002), no. 6, 1051–1107. MR 1923214, https://doi.org/10.1016/S0040-9383(01)00034-9
  • [14] Alfred B. Kempe, On a general method of describing plane curves of the nth degree by linkwork,
    Proc. London Math. Soc. 213 (1876), S1-7(1).
  • [15] Henry C. King, Planar linkages and algebraic sets, Proceedings of 6th Gökova Geometry-Topology Conference, 1999, pp. 33–56. MR 1701638
  • [16] Alexander Kobel, Automated generation of Kempe linkages for algebraic curves in a dynamic geometry system,
    Bachelor's thesis, University of Saarbrücken, 2008.
    Available at https://people.mpi-inf.mpg.de/~akobel/publications/Kobel08-kempe-linkages.pdf.
  • [17] Christoph Koutschan,
    Mathematica package PlanarLinkages.m and electronic supplementary material for the paper Planar linkages following a prescribed motion, this issue, 2016.
    Available at http://www.koutschan.de/data/link/.
  • [18] C. Krattenthaler, Advanced determinant calculus, Sém. Lothar. Combin. 42 (1999), Art. B42q, 67. The Andrews Festschrift (Maratea, 1998). MR 1701596
  • [19] Alain Lascoux and Piotr Pragacz, Jacobians of symmetric polynomials, Ann. Comb. 6 (2002), no. 2, 169–172. MR 1955517, https://doi.org/10.1007/PL00012583
  • [20] Henri Lebesgue, Leçons sur les Constructions Géométriques, Gauthier-Villars, Paris, 1950 (French). MR 0035023
  • [21] Zijia Li, Josef Schicho, and Hans-Peter Schröcker, Factorization of motion polynomials,
    CoRR, abs/1502.07600, 2015.
    Available at http://arxiv.org/abs/1502.07600.
  • [22] Joseph Malkevitch, Linkages: From fingers to robot arms,
    AMS Feature Column, September 2002.
    Available at http://www.ams.org/samplings/feature-column/fcarc-linkages1.
  • [23] Joseph O’Rourke, How to fold it, Cambridge University Press, Cambridge, 2011. The mathematics of linkages, origami, and polyhedra. MR 2768138
  • [24] John Owen and Stephen Power, Continuous curves from infinite Kempe linkages, Bull. Lond. Math. Soc. 41 (2009), no. 6, 1105–1111. MR 2575341, https://doi.org/10.1112/blms/bdp087
  • [25] Mark Plecnik, J. Michael McCarthy, and Charles W. Wampler, Kinematic Synthesis of a Watt I Six-Bar Linkage for Body Guidance,
    In Advances in Robot Kinematics, Springer International Publishing, 2014, pp. 317-325.
  • [26] J. M. Selig, Geometric fundamentals of robotics, 2nd ed., Monographs in Computer Science, Springer, New York, 2005. MR 2250553

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 70B15, 68W30, 70G55, 20G20, 16Z05, 14P05, 12Y05

Retrieve articles in all journals with MSC (2010): 70B15, 68W30, 70G55, 20G20, 16Z05, 14P05, 12Y05


Additional Information

Matteo Gallet
Affiliation: Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenberger Straße 69, 4040 Linz, Austria
Email: matteo.gallet@ricam.oeaw.ac.at

Christoph Koutschan
Affiliation: Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenberger Straße 69, 4040 Linz, Austria
Email: christoph.koutschan@ricam.oeaw.ac.at

Zijia Li
Affiliation: Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenberger Straße 69, 4040 Linz, Austria
Email: zijia.li@ricam.oeaw.ac.at

Georg Regensburger
Affiliation: Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenberger Straße 69, 4040 Linz, Austria
Email: georg.regensburger@ricam.oeaw.ac.at

Josef Schicho
Affiliation: Research Institute for Symbolic Computation (RISC), Johannes Kepler University, Altenberger Straße 69, 4040 Linz, Austria
Email: josef.schicho@ricam.oeaw.ac.at

Nelly Villamizar
Affiliation: Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenberger Straße 69, 4040 Linz, Austria
Email: nelly.villamizar@ricam.oeaw.ac.at

DOI: https://doi.org/10.1090/mcom/3120
Received by editor(s): February 19, 2015
Received by editor(s) in revised form: June 13, 2015
Published electronically: April 13, 2016
Additional Notes: The first, second, and third authors were supported by the Austrian Science Fund (FWF): W1214.
The first author was also supported by the Austrian Science Fund (FWF): P26607 - “Algebraic Methods in Kinematics: Motion Factorisation and Bond Theory”
The fourth author was supported by the Austrian Science Fund (FWF): P27229.
Article copyright: © Copyright 2016 American Mathematical Society