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.
- 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
- 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
- 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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/S0040-9383%2801%2900034-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 https://doi.org/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
- John Owen and Stephen Power, Continuous curves from infinite Kempe linkages, Bull. Lond. Math. Soc. 41 (2009), no. 6, 1105–1111. MR 2575341, DOI https://doi.org/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
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
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.
Article copyright:
© Copyright 2016
American Mathematical Society