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.
- [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
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
