Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Planar linkages following a prescribed motion
HTML articles powered by AMS MathViewer

by Matteo Gallet, Christoph Koutschan, Zijia Li, Georg Regensburger, Josef Schicho and Nelly Villamizar PDF
Math. Comp. 86 (2017), 473-506 Request permission

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
  • 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.
  • Wilhelm Blaschke and Hans R. Müller, Ebene Kinematik, Verlag von R. Oldenbourg, München, 1956.
  • 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, DOI 10.1007/978-3-662-03718-8
  • 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
  • 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.
  • Erik D. Demaine and Joseph O’Rourke, Geometric folding algorithms, Cambridge University Press, Cambridge, 2007. Linkages, origami, polyhedra. MR 2354878, DOI 10.1017/CBO9780511735172
  • 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, DOI 10.1007/BF02948787
  • 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.
  • 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.
  • 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.
  • 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.
  • D. Jordan and M. Steiner, Configuration spaces of mechanical linkages, Discrete Comput. Geom. 22 (1999), no. 2, 297–315. MR 1698549, DOI 10.1007/PL00009462
  • Michael Kapovich and John J. Millson, Universality theorems for configuration spaces of planar linkages, Topology 41 (2002), no. 6, 1051–1107. MR 1923214, DOI 10.1016/S0040-9383(01)00034-9
  • 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).
  • Henry C. King, Planar linkages and algebraic sets, Proceedings of 6th Gökova Geometry-Topology Conference, 1999, pp. 33–56. MR 1701638
  • 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.
  • 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/.
  • C. Krattenthaler, Advanced determinant calculus, Sém. Lothar. Combin. 42 (1999), Art. B42q, 67. The Andrews Festschrift (Maratea, 1998). MR 1701596
  • Alain Lascoux and Piotr Pragacz, Jacobians of symmetric polynomials, Ann. Comb. 6 (2002), no. 2, 169–172. MR 1955517, DOI 10.1007/PL00012583
  • Henri Lebesgue, Leçons sur les Constructions Géométriques, Gauthier-Villars, Paris, 1950 (French). MR 0035023
  • 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.
  • Joseph Malkevitch, Linkages: From fingers to robot arms, AMS Feature Column, September 2002. Available at http://www.ams.org/samplings/feature-column/fcarc-linkages1.
  • Joseph O’Rourke, How to fold it, Cambridge University Press, Cambridge, 2011. The mathematics of linkages, origami, and polyhedra. MR 2768138, DOI 10.1017/CBO9780511975028
  • John Owen and Stephen Power, Continuous curves from infinite Kempe linkages, Bull. Lond. Math. Soc. 41 (2009), no. 6, 1105–1111. MR 2575341, DOI 10.1112/blms/bdp087
  • 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.
  • J. M. Selig, Geometric fundamentals of robotics, 2nd ed., Monographs in Computer Science, Springer, New York, 2005. MR 2250553
Similar Articles
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
  • MR Author ID: 1094242
  • 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
  • MR Author ID: 978116
  • 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
  • MR Author ID: 332588
  • 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
  • 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.
  • © Copyright 2016 American Mathematical Society
  • 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
  • MathSciNet review: 3557808